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?
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).