C++로 숫자 N의 모든 비트 AND 부분 집합(서브마스크) 출력하기

이 문제에서는 0부터 n 사이의 숫자 중, n의 이진수 표현에 포함된 비트만으로 구성된 모든 숫자, 즉 n의 부분 마스크(submask)에 해당하는 값들을 출력해야 합니다. 어떤 수 i가 n의 부분 마스크라는 것은 i & n == i가 성립한다는 의미입니다.

개념을 더 잘 이해하기 위해 예제를 살펴보겠습니다.

입력 : N = 4
출력 : 0 4
설명 :
    0 & 4 = 0      → 0은 4의 부분 마스크 (포함)
    1 & 4 = 0 ≠ 1  (제외)
    2 & 4 = 0 ≠ 2  (제외)
    3 & 4 = 0 ≠ 3  (제외)
    4 & 4 = 4      → 4는 4의 부분 마스크 (포함)

N = 6(이진수 110)인 경우에는 6의 켜진 비트 조합으로 만들 수 있는 0(000), 2(010), 4(100), 6(110)이 모두 해당되므로 출력은 0, 2, 4, 6이 됩니다.

접근 방법

이 문제는 비트 연산자를 활용하면 매우 효율적으로 해결할 수 있습니다. 핵심은 n부터 시작하여 갱신 규칙 i = (i-1) & n을 적용하며 역순으로 반복하는 것입니다. 이 규칙은 현재 값의 가장 낮은 설정 비트를 지우면서 항상 n의 비트 조합 범위 안에 머무르게 하므로, n의 모든 부분 마스크를 내림차순으로 빠짐없이 한 번씩 방문할 수 있습니다.

알고리즘

1단계 : n부터 1까지 반복하되, 일반적인 감소 연산 대신 i = (i-1) & n으로 i를 갱신한다.
2단계 : 각 반복에서 현재 i를 출력한다.
3단계 : 루프가 종료되면 마지막으로 0을 출력한 뒤 프로그램을 끝낸다.

구현 예제

위 알고리즘을 C++로 구현한 프로그램은 다음과 같습니다.

#include <iostream>
using namespace std;

int main() {
    int n = 11;
    for (int i = n; i > 0; i = (i - 1) & n)
        cout << i << " ";
    cout << 0;
    return 0;
}

실행 결과

11 10 9 8 3 2 1 0

동작 원리

n = 11(이진수 1011)일 때 코드는 11 → 10 → 9 → 8 → 3 → 2 → 1 → 0 순서로 부분 마스크를 방문합니다. 예를 들어 (11-1) & 11 = 10, (10-1) & 11 = 9처럼 진행되며, 이 과정에서 n의 비트 패턴을 벗어나는 값은 한 번도 나타나지 않습니다.

시간 복잡도

n의 설정 비트 개수를 k라 할 때 전체 시간 복잡도는 O(2^k)입니다. 0부터 n까지 모든 수를 하나씩 검사하는 O(n) 완전 탐색보다, 설정 비트가 적은 n에 대해서는 훨씬 적은 연산으로 답을 구할 수 있다는 점이 이 기법의 큰 장점입니다.