구현

이 장에서는 켜진 비트 수를 세는 popcount와 비트마스크로 모든 부분집합을 만드는 루틴을 구현합니다. 먼저 Python으로 한 줄씩 설명하고, 같은 루틴을 C++, Java, TypeScript로 옮기며 언어마다 다른 정수 폭과 시프트 규칙을 짚습니다.

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는 음수를 거부합니다. Python 정수는 크기 제한이 없고 음수는 왼쪽으로 1이 끝없이 이어진 것처럼 동작하므로 x &= x - 1을 반복해도 0에 닿지 않습니다.
• x &= x - 1은 최하위 1비트를 하나 지웁니다. 반복 횟수가 곧 켜진 비트 수입니다.
• range(1 << n)은 0부터 2^n - 1까지, n비트로 만들 수 있는 모든 마스크입니다.
• (mask >> i) & 1이 1이면 i번 원소를 고릅니다.
• yield로 하나씩 내보내므로 2^n개의 부분집합을 한꺼번에 메모리에 올리지 않습니다.
• subsets_of_size는 popcount가 k인 마스크만 남겨 크기 k인 조합을 만듭니다.
• 마지막 assert는 결과가 내장 int.bit_count()(Python 3.10 이상)와 같은지 확인합니다. 실무에서는 내장 함수가 더 빠릅니다.

C++ 구현

마스크는 부호 없는 정수로 다룹니다. 부호 있는 정수의 오버플로와 타입 폭 이상의 시프트(1u << 32)는 정의되지 않은 동작입니다. C++20의 <bit>에는 std::popcount가 있고, GCC와 Clang에는 __builtin_popcount와 __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"}); }

Java 구현

int는 32비트, long은 64비트입니다. >>는 부호 비트를 채우고 >>>는 0을 채웁니다. 시프트 횟수는 하위 5비트만 쓰므로 1 << 32는 1이고, 31개를 넘는 원소에는 long과 1L << i가 필요합니다. 표준 라이브러리에는 Integer.bitCount와 Long.bitCount가 있습니다.

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    static int popcount(int x) {
        int count = 0;
        while (x != 0) {
            x &= x - 1; // clear the lowest set bit
            count++;
        }
        return count;
    }

    static void printSubsets(List<String> items) {
        int n = items.size(); // n < 31 for int masks
        for (int mask = 0; mask < (1 << n); mask++) {
            List<String> chosen = new ArrayList<>();
            for (int i = 0; i < n; i++)
                if (((mask >>> i) & 1) == 1) chosen.add(items.get(i));
            System.out.println(mask + " (" + popcount(mask) + "): " + chosen);
        }
    }

    public static void main(String[] args) {
        printSubsets(List.of("a", "b", "c"));
        System.out.println(popcount(-1) + " " + Integer.bitCount(-1)); // 32 32
    }
}

TypeScript 구현

비트 연산자는 숫자를 32비트 부호 있는 정수로 바꿔 계산합니다. 그래서 1 << 31은 음수이고, >>> 0을 붙여야 부호 없는 값으로 읽힙니다. 원소가 30개를 넘으면 BigInt(1n << 40n)를 쓰는데, BigInt에는 >>>가 없습니다.

function popcount(x: number): number {
  let v = x >>> 0; // view as unsigned 32-bit
  let count = 0;
  while (v !== 0) {
    v = (v & (v - 1)) >>> 0; // clear the lowest set bit
    count++;
  }
  return count;
}

function printSubsets<T>(items: readonly T[]): void {
  const n = items.length; // n <= 30, otherwise use BigInt
  for (let mask = 0; mask < 1 << n; mask++) {
    const chosen = items.filter((_, i) => (mask >> i) & 1);
    console.log(`${mask} (${popcount(mask)}):`, chosen);
  }
}

printSubsets(["a", "b", "c"]);
console.log(popcount(-1)); // 32

정리

네 언어 모두 x &= x - 1로 1비트를 지우며 세고, 0부터 (1 << n) - 1까지 마스크를 돌며 (mask >> i) & 1로 원소를 고릅니다. 차이는 정수 폭입니다. Python은 음수를, C++는 부호 없는 타입을, Java는 >>>와 long을, TypeScript는 32비트 변환과 >>> 0을 기억하면 됩니다.