•  06-07-2019
  •  | 
  •  

题

我试图找到一个从0到2 n -1计数的算法，但它们的位模式相反。我只关心一个单词的n LSB。你可能已经猜到我失败了。

对于n = 3：

000 -> 0
100 -> 4
010 -> 2
110 -> 6
001 -> 1
101 -> 5
011 -> 3
111 -> 7

你明白了。

伪代码中的答案很棒。欢迎任何语言的代码片段，首选无位操作的答案。

请不要在没有简短说明或指向信号源的指针的情况下发布片段。

编辑：我忘了添加，我已经有一个天真的实现，只是反转计数变量。从某种意义上说，这种方法并不算数。

有帮助吗？

解决方案

即使您说这不是首选，我觉得最简单的位操作

假设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);

基本上，这会对所有位进行交错的混乱。每次大约一半的值与另一半交换。

最后一行是重新对齐位以使bin <！>“n <！>”;是最重要的一点。

如果<！>“; n <！>”，则可以使用更短的版本。是<！> lt; = 16，或<！> lt; = 8

其他提示

在每个步骤中，找到值的最左边的0位数。设置它，并清除它左侧的所有数字。如果你没有找到0位数，那么你已经溢出：返回0，或停止，或崩溃，或任何你想要的。

这是在正常的二进制增量上发生的（我的意思是它的效果，而不是它在硬件中的实现方式），但是我们在左边而不是右边进行。

无论你是在比特操作，字符串还是其他方面都这样做，都取决于你。如果你在bitops中这样做，那么~value上的clz（或调用等效的hibit风格的函数）可能是最有效的方式：__ builtin_clz（如果可用）。但这是一个实施细节。

此解决方案最初是二进制的，并按照请求者的指定转换为常规数学。

它更有意义，因为二进制，至少乘以2除以2应该是<！> lt; <！> lt; 1和<！> gt; <！> gt; 1对于速度，加法和减法可能无关紧要。

如果传入掩码而不是nBits，并使用bitshifting而不是乘法或除法，并将尾递归更改为循环，这可能是您找到的最高性能解决方案，因为每次其他调用都不会是但是只需要一次添加，它就会像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

以下是我的解答不同的解决方案问题，计算下一个位反转索引而不循环。不过，它在很大程度上依赖于位操作。

关键思想是递增数字只是翻转一系列最低有效位，例如从nnnn0111到nnnn1000。因此，为了计算下一个位反转索引，您必须翻转一系列最重要的位。如果您的目标平台具有CTZ（<！> quot; count trailing zeros <！> quot;）指令，则可以有效地完成此操作。

使用GCC __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;
    }
}

如果没有CTZ指令，您也可以使用整数除法：

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);
    }
}

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);
}

可能从0递增到N（<！> quot;通常<！>“;方式<！>”;）并为每次迭代执行ReverseBitOrder（）。你可以找到几个实现这里（我喜欢LUT一个最好）。 应该很快。

这是Perl的答案。你没有说出所有模式后面的内容，所以我只返回零。我取出了按位操作，因此很容易翻译成另一种语言。

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;
}

这是一个实际上没有尝试进行任何添加的解决方案，但是利用了序列的开/关模式（每次大多数sig位交替，下一个大多数sig位每隔一次交替等），调整n为期望的：

#define FLIP(x, i) do { (x) ^= (1 << (i)); } while(0)

int main() {
    int n   = 3;
    int max = (1 << n);
    int x   = 0;

    for(int i = 1; i <= max; ++i) {
        std::cout << x << std::endl;
        /* if n == 3, this next part is functionally equivalent to this:
         *
         * if((i % 1) == 0) FLIP(x, n - 1);
         * if((i % 2) == 0) FLIP(x, n - 2);
         * if((i % 4) == 0) FLIP(x, n - 3);
         */
        for(int j = 0; j < n; ++j) {
            if((i % (1 << j)) == 0) FLIP(x, n - (j + 1));
        }                       
    }
}

如果需要，如何向最高有效位添加1，然后进入下一个（不太重要）位。您可以通过操作字节来加快速度：

  1. 预先计算查找表，用于从0到256的位反转计数（00000000 - <！>> 10000000,10000000 - <！> gt; 01000000，...，11111111 - <！>> 00000000）。
  2. 将多字节数中的所有字节设置为零。
  3. 使用查找表增加最重要的字节。如果字节为0，则使用查找表递增下一个字节。如果字节为0，则递增下一个字节...
  4. 转到第3步。

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))))))

当您反转0 to 2^n-1但其位模式反转时，您几乎涵盖了整个0-2^n-1序列

Sum = 2^n * (2^n+1)/2

O(1)操作。无需进行反转

编辑：当然，原始海报的问题是要通过（反向）增量来增加，这使得事情比添加两个随机值更简单。所以nwellnhof的答案已包含该算法。

求和两位反转值

以下是php中的一个解决方案：

function RevSum ($a,$b) {

    // loop until our adder, $b, is zero
    while ($b) {

        // get carry (aka overflow) bit for every bit-location by AND-operation
        // 0 + 0 --> 00   no overflow, carry is "0"
        // 0 + 1 --> 01   no overflow, carry is "0"
        // 1 + 0 --> 01   no overflow, carry is "0"
        // 1 + 1 --> 10   overflow! carry is "1"

        $c = $a & $b;


        // do 1-bit addition for every bit location at once by XOR-operation
        // 0 + 0 --> 00   result = 0
        // 0 + 1 --> 01   result = 1
        // 1 + 0 --> 01   result = 1
        // 1 + 1 --> 10   result = 0 (ignored that "1", already taken care above)

        $a ^= $b;


        // now: shift carry bits to the next bit-locations to be added to $a in
        // next iteration.
        // PHP_INT_MAX here is used to ensure that the most-significant bit of the
        // $b will be cleared after shifting. see link in the side note below.

        $b = ($c >> 1) & PHP_INT_MAX;

    }

    return $a;
}

旁注：请参阅此问题关于转移负值。

至于测试;从零开始，将值增加8位反转（10000000）：

$value = 0;
$add = 0x80;    // 10000000 <-- "one" as bit reversed

for ($count = 20; $count--;) {      // loop 20 times
    printf("%08b\n", $value);       // show value as 8-bit binary
    $value = RevSum($value, $add);  // do addition
}

...将输出：

 00000000
 10000000
 01000000
 11000000
 00100000
 10100000
 01100000
 11100000
 00010000
 10010000
 01010000
 11010000
 00110000
 10110000
 01110000
 11110000
 00001000
 10001000
 01001000
 11001000
许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top