如何遍历由位表示的集合的所有子集？
How is it possible to iterate over all subsets of a set represented by bits?
我正在浏览 this article 它解释了
It is also possible to iterate over all the subsets of a particular subset (represented by a bit pattern), provided that you don’t mind visiting them in reverse order (if this is problematic, put them in a list as they’re generated, then walk the list backwards). The trick is similar to that for finding the lowest bit in a number. If we subtract 1 from a subset, then the lowest set element is cleared, and every lower element is set. However, we only want to set those lower elements that are in the superset. So the iteration step is just i = (i - 1) & superset.
看了好几遍还是没看懂。有人可以举例说明吗？
如果我们有一些表示为位掩码的集合，例如，如果我们有宇宙：
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 }，暂时删除 B。那么接下来是
i1 = 0b1101100
i2 = i1 - 1 & S = 0b1101100 - 1 & S = 0b1101011 & S = 0b1101010
代表{ B, D, F, G }.
顺便说一下，它可以在不将整个内容存储在列表中的情况下向前完成：
i = ((i | ~S) + 1) & S
这里我们需要额外的| ~S来设置"in between"位，让+ 1通过它们，否则都是一样的想法。
我正在浏览 this article 它解释了
It is also possible to iterate over all the subsets of a particular subset (represented by a bit pattern), provided that you don’t mind visiting them in reverse order (if this is problematic, put them in a list as they’re generated, then walk the list backwards). The trick is similar to that for finding the lowest bit in a number. If we subtract 1 from a subset, then the lowest set element is cleared, and every lower element is set. However, we only want to set those lower elements that are in the superset. So the iteration step is just i = (i - 1) & superset.
看了好几遍还是没看懂。有人可以举例说明吗？
如果我们有一些表示为位掩码的集合，例如，如果我们有宇宙：
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 }，暂时删除 B。那么接下来是
i1 = 0b1101100
i2 = i1 - 1 & S = 0b1101100 - 1 & S = 0b1101011 & S = 0b1101010
代表{ B, D, F, G }.
顺便说一下，它可以在不将整个内容存储在列表中的情况下向前完成：
i = ((i | ~S) + 1) & S
这里我们需要额外的| ~S来设置"in between"位，让+ 1通过它们，否则都是一样的想法。