algorithm - 计数，反转位模式

Question

我正在尝试找到一种从 0 计数到 2ⁿ-1 的算法，但它们的位模式颠倒了。我只关心一个词的 n LSB。您可能已经猜到我失败了。

对于 n=3:

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

你明白了。

伪代码答案很棒。欢迎任何语言的代码片段，最好没有位操作的答案。

请不要只发布片段，甚至没有简短的解释或指向源的指针。

编辑:我忘了补充，我已经有了一个简单的实现，它只是对计数变量进行位反转。从某种意义上说，这种方法并不算数。

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

本质上，这是对所有位进行交错洗牌。每次值中大约一半的位与另一半交换。

最后一行是重新对齐位所必需的，以便 bin "n"是最高有效位。

如果“n”为 <= 16 或 <= 8，则可以使用更短的版本