我读了for ( x = y; x > 0; x = ( y & (x-1) ) )
生成位掩码 y 的所有子集。
此迭代如何工作？有什么直观的解释吗？
来源： http://codeforces.com/blog/entry/45223
请参阅次优解决方案部分。
直觉：作为一个数字，位掩码y不能有超过y个子集。因此，通过倒计时x，您可以保证通过位掩码击中y的每个子集。但这会产生很多重复项。想想1101.如果你从那里倒计时并用y掩饰，序列就会消失。1101、1100、1001、1000、1001、1000等。通过x分配掩码操作的结果，可以跳到其最后一次出现。
证明：这导致通过归纳进行简单的证明。显然，对于长度为 1 的位字符串，此过程有效。只有两个子集，1和0，按该顺序发出。
现在假设此过程适用于长度为N的位串。假设Z是长度为N的位串。如果创建位串0Z，则遵循与Z相同的顺序，因为减法永远不会打开高阶位。如果创建位串1Z，则会发生以下情况： 对于前2^nnz(Z)步，遵循原始Z序列，并附加1。对于最后2^nnz(Z)步骤，遵循原始Z序列，并附加0。由于该过程两次访问较小序列的每个元素，第一次1前面，第二次0，因此我们得出结论，该过程发出1Z的每个子集。
综上所述，我们看到该过程适用于所有位字符串。
这里使用的第一个简单事实是，如果我们7取值(二进制111)并开始反复递减(一直到0)，我们将通过二进制表示
111, 110, 101, 100, 011, 010, 001, 000
它以一种相当明显的方式表示原始 3 集的所有可能子集。
第二个事实是，在二进制中，"递减x"("从x中减去1")的意思是：反转x的所有位，从最不重要的(最右边)开始，向左反转，直到(并包括)x表示的第一个1。向左"在这里的意思是"在增加位重要性的方向上"。
例如
00001000 - 1 = 00000111, i.e. we invert the `1000` tail
01010101 - 1 = 01010100, i.e. we invert just the `1` tail
10000000 - 1 = 01111111, i.e. we invert the whole thing
and so on
递减操作"关闭"二进制表示中最不重要的1位，并"打开"其右侧的所有零位。
现在，第三个事实是，在您的情况下1位x始终是1位y的子集，因为我们从x = y开始，并在每次迭代中执行x = (whatever) & y。
当我们执行x - 1时，我们"关闭"(设置为0)x中最低1，并"打开"(设置为1)所有0x从该最低1向右。
当我们在x = (x - 1) & y中遵循& y时，我们会"关闭">x中的一些原始y位，并在x中"打开"所有较低的原始y位。
在这一点上，应该已经相当明显地表明，这个操作只是x的"掩蔽递减"：通过这样做x = (x - 1) & y我们只是在假设只有被y掩蔽的位形成x的值，而所有其他位只是可以忽略不计的"填充位"的情况下减少x的值。
为了与上面的例子平行，递减7，y的初始值可能看起来10010100。操作x = (x - 1) & y将此值视为某种"分布式 7"(非正式地说)。x将继续执行以下值
1..1.1.., 1..1.0.., 1..0.1.., 1..0.0.., 0..1.1.., 0..1.0.., 0..0.1.., 0..0.0..
其中.指定x的"填充"位"，它们并不真正参与这种"屏蔽递减"操作(实际上它们将被0)。请注意与原始示例的相似性7.