对特定子集的位操作

Question

考虑以下代码片段。

    for (int state = 1; state < 1 << n; state ++ )
        if (state & 1)
            for (int t = state; t; t &= t - 1)

第一个for循环是枚举n个元素的所有子集，但是t代表什么子集

Answer 1

for (int t = state; t; t &= t - 1)

此循环正在从 t 中逐一删除 least-significant 1 位。

所以 state 的初始值如 63（二进制 111111）将变为 62（111110），然后是 60，（111100），56（ 111000), 48 (110000), 32, (100000), 最后是 0.

bit manipulation to specific subset