我正在尝试寻找一种算法，可以将从0到2n-1的数字按位反转。我只关心一个字中最低有效位（LSB）的值。但是你可能已经猜到了，我失败了。
以n=3为例：
000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7
nnnn0111 到 nnnn1000。因此，为了计算下一个反转位索引，您必须翻转一系列最重要的位。如果您的目标平台具有 CTZ（“count trailing zeros”）指令，则可以高效地完成此操作。__builtin_ctz 的 C 示例：void iter_reversed(unsigned bits) {
unsigned n = 1 << bits;
for (unsigned i = 0, j = 0; i < n; i++) {
printf("%x\n", j);
// Compute a mask of LSBs.
unsigned mask = i ^ (i + 1);
// Length of the mask.
unsigned len = __builtin_ctz(~mask);
// Align the mask to MSB of n.
mask <<= bits - len;
// XOR with mask.
j ^= mask;
}
}
void iter_reversed(unsigned bits) {
unsigned n = 1 << bits;
for (unsigned i = 0, j = 0; i < n; i++) {
printf("%x\n", j);
// Find least significant zero bit.
unsigned bit = ~i & (i + 1);
// Using division to bit-reverse a single bit.
unsigned rev = (n / 2) / bit;
// XOR with mask.
j ^= (n - 1) & ~(rev - 1);
}
}
我认为最简单的方法是使用位运算，虽然你说不喜欢这种方法。
假设是32位整数，在这里有一个很棒的代码块可以在不使用32步的情况下翻转所有位:
unsigned int i;
i = (i & 0x55555555) << 1 | (i & 0xaaaaaaaa) >> 1;
i = (i & 0x33333333) << 2 | (i & 0xcccccccc) >> 2;
i = (i & 0x0f0f0f0f) << 4 | (i & 0xf0f0f0f0) >> 4;
i = (i & 0x00ff00ff) << 8 | (i & 0xff00ff00) >> 8;
i = (i & 0x0000ffff) << 16 | (i & 0xffff0000) >> 16;
i >>= (32 - n);
本质上，这是对所有位进行交错洗牌。每次循环，该值中一半的位数与另一半交换。
最后一行是必要的，以重新对齐位，使二进制“n”成为最高位。
如果“n”≤16或≤8，则可以使用更短的版本。
每一步，找到值中最左边的 0 位数字。将其设置为 1，并清除其左侧的所有位数。如果您没有找到 0 位数字，则表示您已经溢出：请返回 0，或停止，或崩溃，或任何您想要的操作。
这就是正常的二进制增量发生的情况（我的意思是它的效果，而不是它在硬件上如何实现），但我们是在左边而不是右边执行它。
无论您是在位运算、字符串还是其他方式中执行此操作，都由您决定。如果您使用位运算执行此操作，则对~value进行 clz（或调用等效 hibit 类型函数）可能是最有效的方法：__builtin_clz（如果可用）。但这只是一个实现细节。
根据请求者的要求，这个解决方案最初是以二进制形式呈现的，然后转换为常规数学形式。
虽然加减法可能不会有什么影响，但至少乘以2和除以2应该改为<<1和>>1以提高速度，如果使用掩码而不是nBits，并使用位移而不是乘除法，并将尾递归改为循环，则此解决方案可能是您能找到的性能最佳的解决方案，因为每次调用都只需要进行一次加法操作，它只会像Alnitak的解决方案一样变慢，每4次甚至8次调用一次。
int incrementBizarre(int initial, int nBits)
// in the 3 bit example, this should create 100
mask=2^(nBits-1)
// This should only return true if the first (least significant) bit is not set
// if initial is 011 and mask is 100
// 3 4, bit is not set
if(initial < mask)
// If it was not, just set it and bail.
return initial+ mask // 011 (3) + 100 (4) = 111 (7)
else
// it was set, are we at the most significant bit yet?
// mask 100 (4) / 2 = 010 (2), 001/2 = 0 indicating overflow
if(mask / 2) > 0
// No, we were't, so unset it (initial-mask) and increment the next bit
return incrementBizarre(initial - mask, mask/2)
else
// Whoops we were at the most significant bit. Error condition
throw new OverflowedMyBitsException()
哇，这个结果看起来很酷。我直到最后一秒才想到递归。
感觉有些不对——好像有些操作不应该起作用，但由于你所做的事情的性质（就像感觉当你在操作一个位时，左边的一些位是非零的，你应该会遇到麻烦，但事实证明，除非所有左边的位都是零，否则你永远不可能操作一个位——这是一个非常奇怪的条件，但却是真实的。
从110到001的流程示例（向后3个到向后4个）：
mask 100 (4), initial 110 (6); initial < mask=false; initial-mask = 010 (2), now try on the next bit
mask 010 (2), initial 010 (2); initial < mask=false; initial-mask = 000 (0), now inc the next bit
mask 001 (1), initial 000 (0); initial < mask=true; initial + mask = 001--correct answer
当你反转0到2^n-1，但是它们的位模式被反转时，你几乎涵盖了整个0-2^n-1序列。
Sum = 2^n * (2^n+1)/2
O(1) 操作。无需进行位反转。
如果需要，可以将1添加到最高位，然后将其进位到下一个（低位）比特。您可以通过操作字节来加快此过程：
void reverse(int nMaxVal, int nBits)
{
int thisVal, bit, out;
// Calculate for each value from 0 to nMaxVal.
for (thisVal=0; thisVal<=nMaxVal; ++thisVal)
{
out = 0;
// Shift each bit from thisVal into out, in reverse order.
for (bit=0; bit<nBits; ++bit)
out = (out<<1) + ((thisVal>>bit) & 1)
}
printf("%d -> %d\n", thisVal, out);
}
sub reverse_increment {
my($n, $bits) = @_;
my $carry = 2**$bits;
while($carry > 1) {
$carry /= 2;
if($carry > $n) {
return $carry + $n;
} else {
$n -= $carry;
}
}
return 0;
}
若 n 为 2 的幂次方，x 为你想要步进的变量：
(defun inv-step (x n) ; the following is a function declaration
"returns a bit-inverse step of x, bounded by 2^n" ; documentation
(do ((i (expt 2 (- n 1)) ; loop, init of i
(/ i 2)) ; stepping of i
(s x)) ; init of s as x
((not (integerp i)) ; breaking condition
s) ; returned value if all bits are 1 (is 0 then)
(if (< s i) ; the loop's body: if s < i
(return-from inv-step (+ s i)) ; -> add i to s and return the result
(decf s i)))) ; else: reduce s by i
我对它进行了详细的注释，因为你可能不熟悉这个语法。
编辑：这是尾递归版本。如果你有一个支持尾调用优化的编译器，它似乎会快一点。
(defun inv-step (x n)
(let ((i (expt 2 (- n 1))))
(cond ((= n 1)
(if (zerop x) 1 0)) ; this is really (logxor x 1)
((< x i)
(+ x i))
(t
(inv-step (- x i) (- n 1))))))