CODEWITHSUNDEEP
c++bit-manipulation
John London
John London

Reputation: 1412

Subset related bit manipulation

I want to know what this bit manipulation means:

for (int m = 1; m < (1 << n); ++m) {
    for (int s = m; s; s = (s - 1) & m) {
        // ....
    }
}

The first for-loop is to enumerate all subsets of n elements, but what the second for-loop means?

Upvotes: 5

Views: 303

Answers (1)

Max Langhof
Max Langhof

Reputation: 23681

If s is of the form ...10000 then s-1 is ...01111. We then & with m, which leaves only those 1 in the lower portion that were also present in m. (The upper bits of s stay untouched and remain identical to those in m).

Effectively, we clear the least set bit in s and replace all lower bits with those in m. It can be seen that this amounts to "counting downwards within the set bits of m". That is, if m has k set bits, count down from (1<<k)-1 and, for each of those 2k numbers, distribute its k bits into the k positions that m had set bits in.

Or, if we interpret m as a bitset, it enumerates all subsets of m (including m but skipping the empty subset).

Upvotes: 3

Related Questions