计数,反转位模式

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，则可以使用更短的版本