Implementation

This chapter implements two core routines: popcount, which counts set bits, and a subset enumerator driven by bitmasks. We walk through the Python version line by line, then port the same routine to C++, Java and TypeScript, noting where integer width and shift rules differ.

Python

from collections.abc import Iterator, Sequence


def popcount(x: int) -> int:
    if x < 0:
        raise ValueError("x must be non-negative")
    count = 0
    while x:
        x &= x - 1          # clear the lowest set bit
        count += 1
    return count


def subsets(items: Sequence) -> Iterator[tuple[int, list]]:
    n = len(items)
    for mask in range(1 << n):                  # 0 .. 2^n - 1
        chosen = [items[i] for i in range(n) if (mask >> i) & 1]
        yield mask, chosen


def subsets_of_size(items: Sequence, k: int) -> list[list]:
    return [chosen for mask, chosen in subsets(items) if popcount(mask) == k]


if __name__ == "__main__":
    for mask, chosen in subsets(["a", "b", "c"]):
        print(format(mask, "03b"), popcount(mask), chosen)
    print(subsets_of_size(["a", "b", "c", "d"], 2))
    assert all(popcount(m) == m.bit_count() for m in range(1 << 12))

• popcount rejects negative input. Python integers are unbounded and a negative value behaves as if it had infinitely many leading 1s, so x &= x - 1 would never reach 0.
• x &= x - 1 clears the lowest set bit; the number of rounds is the answer.
• range(1 << n) yields every n-bit mask, from 0 to 2^n - 1.
• (mask >> i) & 1 tests bit i; when it is 1, items[i] is in the subset.
• yield produces subsets one at a time, so all 2^n of them never sit in memory together.
• subsets_of_size keeps masks whose popcount is k, giving all k-combinations.
• The final assert checks against the built-in int.bit_count() (Python 3.10+), which is what you should use in production.

C++

Use unsigned types for masks. Signed overflow and shifting by the full width or more (1u << 32) are undefined behavior. C++20 adds std::popcount in <bit>, and GCC and Clang offer __builtin_popcount and __builtin_ctz.

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

int popcount(std::uint32_t x) {
    int count = 0;
    while (x != 0) {
        x &= x - 1;  // clear the lowest set bit
        ++count;
    }
    return count;
}

void printSubsets(const std::vector<std::string>& items) {
    const int n = static_cast<int>(items.size());  // n < 32
    for (std::uint32_t mask = 0; mask < (1u << n); ++mask) {
        std::cout << mask << " (" << popcount(mask) << "):";
        for (int i = 0; i < n; ++i)
            if ((mask >> i) & 1u) std::cout << ' ' << items[i];
        std::cout << '\n';
    }
}

int main() { printSubsets({"a", "b", "c"}); }