子集相关位运算疑问：双层循环内层循环的含义是什么

Great question! Let’s break down exactly what that inner loop does—it’s a clever bitwise trick that’s a staple in combinatorial programming.

First, as you noted, the outer loop for (int m = 1; m < (1 << n); ++m) iterates over every non-empty subset of your n elements: each bit in m acts as a flag for whether an element is included in the subset.

What the Inner Loop Does #

The inner loop for (int s = m; s; s = (s - 1) & m) is designed to iterate over all non-empty subsets of the current subset m.

Let’s unpack the magic of s = (s - 1) & m:

• When you subtract 1 from s, you flip the rightmost set bit to 0 and all bits to its right to 1. For example, 1010 minus 1 becomes 1001.
• ANDing that result with m clears any bits that weren’t set in m—this ensures we never generate a subset that includes elements not present in m. Using the same example, 1001 & 1010 gives 1000, which is a valid subset of m.

This trick efficiently steps through every possible non-empty subset of m without duplicates, and runs in O(2^k) time where k is the number of set bits in m—way more efficient than brute-forcing all possible combinations.

Example Walkthrough #

Let’s take m = 1010 (binary, representing elements 2 and 4 in a 0-indexed set):

1. First iteration: s = 1010 (the full subset itself)
2. Next: s = (1010 - 1) & 1010 = 1001 & 1010 = 1000 (only element 4)
3. Next: s = (1000 - 1) & 1010 = 0111 & 1010 = 0010 (only element 2)
4. Finally: s = (0010 - 1) & 1010 = 0001 & 1010 = 0, so the loop exits.

Another example with m = 111 (binary, 3 elements):
The inner loop will generate 111, 110, 101, 100, 011, 010, 001—all 7 non-empty subsets of the 3-element parent subset.

This pattern is incredibly useful for problems where you need to check subsets within subsets, like finding all possible valid sub-groups within every possible group of elements.

内容的提问来源于stack exchange，提问作者John London