问比特掩码技术
EN

Stack Overflow用户

提问于 2017-07-29 18:43:41

回答 3查看 167关注 0票数 1

我遇到了以下循环：

int i=a;
while (i!=0) {
  i = (i-1) & a;
}

它的意义是什么？是否打印a的所有子集

algorithm

bit-manipulation

音视频低代码开发方案最快1天上线

推出 TUICallKit 和 TUIRoomKit 低代码集成方案，最快1天接入在线教育、语聊房、在线客服等应用

回答 3

Stack Overflow用户

发布于 2017-07-29 19:02:55

and-with-value- Meaning的含义

使用“与值减1进行a运算”的模式来剥离最低设置位：

1101110000000101000         # value
               ^---- bottomost set bit   
1101110000000100111         # value minus one
                  ^-- set to one
                 ^--- set to one
                ^---- set to one
               ^----- reset to zero

减一步将最底层的设置位置零，并将其下面的所有位设置为1。

然后，随后的and操作将新置零的位应用回a。零化值右侧的位保持不变(与1进行a运算会保留一点不变)。

整体模式

循环将最底层的位置零，并“恢复”该位右侧的所有位。因此，OP猜测函数循环遍历了a". 的所有子集，这是正确的

换句话说，代码会生成设置和取消设置的每一位的cartesian product。因此，迭代次数将是2的幂。

示例

例如，从二进制形式为00100101的a = 37开始，我们得到由8个元素组成的序列：[37, 36, 33, 32, 5, 4, 1, 0]。

位值是[32, 4, 1]，它是二进制形式的[00100000, 00000100, 00000001]。

该序列只是乘积的总和。下面是一个简短的Python示例：

>>> from itertools import product
>>> for tup in product([32, 0], [4, 0], [1, 0]):
        print('%2d  = sum(%r) = sum(%r)' % (sum(tup), [format(x, '08b') for x in tup], list(tup)))


37  = sum(['00100000', '00000100', '00000001']) = sum([32, 4, 1])
36  = sum(['00100000', '00000100', '00000000']) = sum([32, 4, 0])
33  = sum(['00100000', '00000000', '00000001']) = sum([32, 0, 1])
32  = sum(['00100000', '00000000', '00000000']) = sum([32, 0, 0])
 5  = sum(['00000000', '00000100', '00000001']) = sum([0, 4, 1])
 4  = sum(['00000000', '00000100', '00000000']) = sum([0, 4, 0])
 1  = sum(['00000000', '00000000', '00000001']) = sum([0, 0, 1])
 0  = sum(['00000000', '00000000', '00000000']) = sum([0, 0, 0])

票数 2

Stack Overflow用户

发布于 2017-07-29 18:58:08

具有三位设置的'a‘的两个示例。

a=i(0)=10101,   a=i(0) = 11010
  i(1)=10100,     i(1) = 11000
  i(2)=10001,     i(2) = 10010
  i(3)=10000,     i(3) = 10000
  i(4)=00101,     i(4) = 01010
  i(5)=00100,     i(5) = 01000
  i(6)=00001,     i(6) = 00010
  i(7)=00000,     i(7) = 00000

实际上，该函数使用与具有与a中的非零比特一样多的比特的任何计数器的步数从' a‘向下计数到0。比特交织到a中的比特位置，这可能具有一些实际应用，例如与Morton数相关，或者生成位于预定比特的序列。

退化的情况是所有位都向右移位(1,3,7,15，...)其中循环简单地转换为while(i--);。

票数 1

Stack Overflow用户

发布于 2017-07-29 19:21:26

该算法将使用0到(n-1)位集合来计算设置a的位的所有可能的子集，其中n是位的总数。第二个规则是，如果a中的比特位置为零，则它将不属于这个子集。

例如，对于a= 0b111 (n = 3)

i = (i-1) & a (i-1 = 110 (6) a = 111 (7) result 110 (6))
i = (i-1) & a (i-1 = 101 (5) a = 111 (7) result 101 (5))
i = (i-1) & a (i-1 = 100 (4) a = 111 (7) result 100 (4))
i = (i-1) & a (i-1 = 011 (3) a = 111 (7) result 011 (3))
i = (i-1) & a (i-1 = 010 (2) a = 111 (7) result 010 (2))
i = (i-1) & a (i-1 = 001 (1) a = 111 (7) result 001 (1))
i = (i-1) & a (i-1 = 000 (0) a = 111 (7) result 000 (0))

您可以在这里看到的是设置a (0b111 =3位设置)与0、1或2位设置的所有组合。

关于第二条规则，请看一下：

i = (i-1) & a (i-1 = 101 (5) a = 110 (6) result 100 (4))
i = (i-1) & a (i-1 = 011 (3) a = 110 (6) result 010 (2))
i = (i-1) & a (i-1 = 001 (1) a = 110 (6) result 000 (0))