遍历非连续的位位置

Question

如何遍历 2^n 值，这些值由给定掩码 m（汉明权重 n）定义的 n 非连续位组成。

示例：16 位变量，n=3，m=0x0103。产生的 2^3=8 值应该是：

    (binary)         (hex)
0000000000000000    0x0000
0000000000000001    0x0001
0000000000000010    0x0002
0000000000000011    0x0003
0000000100000000    0x0100
0000000100000001    0x0101
0000000100000010    0x0102
0000000100000011    0x0103

我相信这可以在 c*2^n 操作中完成，对于小的 c（1 或 2）。

Answer 1

诀窍是如何从前一个值到下一个值。

mask = 0b0000000100000011
invmask = (~mask & (1 << 16) - 1)

curr = 0
for i in range(16):
        print "{0:016b}".format(curr)
        curr = ((curr | invmask) + 1) & mask

它给出：

0000000000000000
0000000000000001
0000000000000010
0000000000000011
0000000100000000
0000000100000001
0000000100000010
0000000100000011
0000000000000000
0000000000000001
0000000000000010
0000000000000011
0000000100000000
0000000100000001
0000000100000010
0000000100000011

感谢您提出这个非常有趣的问题。

遍历非连续的位位置

Loop through non-consecutive bit positions

bit-manipulation