任意位数的高效字节序反转

Question

我有一个长度为 2^n 的列表，其索引的数字最大为 2^n-1，但问题是我想使用按位反向字节序索引对列表重新排序。

例如，如果 n = 4，我想交换索引 0001<->1000、0010<->0100、0011<->1100，依此类推...

到目前为止我看过的解决方案似乎只能反转字节的字节顺序（我对位感兴趣），或者依赖于不起作用的内置函数任意位数。

我目前使用的临时方法（Python/C++）是将每个索引转换为字符串，反转字符串并转换回索引，但这似乎效率很低。执行此操作的更好方法是什么？

Answer 1

执行 bit-reversal permutation 实际上不需要对任何整数进行位反转（这当然是一种实现方式，但不是很好）。那是因为执行实际排列的算法不会要求以无特定顺序的任意位反转整数。有这个序列就可以了 (for n=4)

生成该序列的另一个技巧是使用 i + 1 操作执行最低有效设置位，使它们全部为零，然后设置最低有效未设置位。或者换句话说，它就像操作 "invert the bits starting at the LSB, but stop after inverting the first zero"。该操作可以相对容易地进行位反转，我们只需要通过一些连续设置位的掩码进行异或，其长度可以通过计算 __builtin_ctz(i + 1) + 1 找到（最后的 +1 是包括零在计数中变成了一个）。然后掩码本身可以找到 N - (N >> maskLength) 其中 N 是数组的大小（2 的幂，减去它的移位版本设置从较低位置开始到较高位置的所有位位置）。

例如：（未测试）

for (uint32_t i = 0, rev = 0; i < N; ++i)
{
    if (i < rev)
        swap(X[i], X[rev]);
    int maskLen = __builtin_ctz(i + 1) + 1;
    rev ^= N - (N >> maskLen);
}

__builtin_ctz 适用于 GCC 和 Clang，对于 MSVC，您可以使用 _BitScanForward（它的工作方式略有不同）。

有一个类似的技巧，它使用 i ^ (i + 1) 的前导零计数。

顺便说一下，如果它被用作 FFT 的一部分，您可以考虑使用不需要它的算法，例如自然阶 Cooley-Tukey 算法或 Stockham 自动排序算法。

实际上可以通过先 reversing it totally 然后将其右移 32 - bits （或 64，如果执行 64 位反转）来反转任意 n 位数。对于每个特定的 n 也有一个相应的特殊情况的位操作技巧，但是 n 被作为常量嵌入到代码中。使用完全反向然后移位适用于变量 n。一些 CPU 可能有指令对此有帮助，例如 ARM（实际上是 ARMv6T2 及更高版本）有 RBIT.

任意位数的高效字节序反转

Efficient endianness reversal for arbitrary number of bits

bit-manipulation

endianness