代码之家 › 专栏 › 技术社区 › sofs1 Romain Manni-Bucau

怎么可能迭代一个由位表示的集合的所有子集[[关闭]

bit bit-manipulation

-1

sofs1 Romain Manni-Bucau · 技术社区 · 7 年前

我本来要去的 this article

也可以迭代特定子集(由位模式表示)的所有子集,前提是您不介意以相反的顺序访问它们(如果这有问题,请在生成时将它们放在列表中,然后向后遍历列表)。这个技巧类似于在一个数字中寻找最低位。如果我们从一个子集中减去1,那么最小的集合元素被清除,并且每个较低的元素被集合。但是,我们只想设置超集中较低的元素。所以迭代步骤就是i=(i-1)&超集。

1 回复 | 直到 7 年前

1

user555045 7 年前

如果我们有一个表示为位掩码的集合,例如,如果我们有一个宇宙:

U = { A, B, C, D, E, F, G }

然后是辅音 S = { B, C, D, F, G } 可以表示为0b1101110(从右边读取,最低有效位对应于A),我们可以用以下公式迭代该集合的子集:

i = (i - 1) & S

因为减去1将借用任何尾随的零并取消设置最低的设置位,那么 & S S . 例如:

i0 = 0b1101110 (the whole S)
i1 = i0 - 1 & S = 0b1101110 - 1 & S = 0b1101101 & S = 0b1101100

下一个子集是 { C, D, F, G }

i1 = 0b1101100
i2 = i1 - 1 & S = 0b1101100 - 1 & S = 0b1101011 & S = 0b1101010

代表 { B, D, F, G } .

i = ((i | ~S) + 1) & S

这里我们需要一个额外的 | ~S + 1 坚持到底,否则就是同一个想法。