n개의 원소 중 k개를 선택하는 모든 조합을 순회해야 할 때, 대부분은 itertools.combinations나 재귀 함수를 떠올릴 것입니다. 하지만 비트마스크를 사용해야 하는 상황이라면 Gosper's Hack을 사용할 수 있습니다.
1. 서론
발견 계기
https://www.acmicpc.net/problem/17127
이 알고리즘을 처음 찾게 된 건 "n개를 여러 그룹으로 나누는 모든 경우"를 순회해야 할 때였습니다. n개의 원소를 4개 그룹으로 나눈다면, n-1개의 틈 중 3개를 고르는 문제이고 3중 for문으로 충분합니다.
하지만 그룹 수가 가변이거나 많아지면 어떨까요? k중 for문은 비현실적입니다. 점화식으로 "다음 경우"를 구하려 했는데, 조건문과 반복문이 걸렸습니다. 순수 비트 연산만으로 다음 조합을 O(1)에 구할 수 있는 방법이 있을까? 그렇게 찾은 것이 Gosper's Hack입니다.
문제 상황
비트마스크 DP를 풀다 보면 이런 상황을 마주칩니다:
"n개의 원소 중 정확히 k개가 선택된 모든 부분집합을 순회하고 싶다"
예를 들어, $n = 5$이고 $k = 3$일 때, 다음과 같은 비트마스크들을 순회해야 합니다:
00111 (7)
01011 (11)
01101 (13)
01110 (14)
10011 (19)
10101 (21)
10110 (22)
11001 (25)
11010 (26)
11100 (28)
단순히 0부터 $2^n - 1$까지 순회하면서 popcount가 k인지 체크하는 방법도 있지만, 이는 $O(2^n)$의 시간이 걸립니다. 실제로 필요한 조합의 수는 $\binom{n}{k}$개뿐인데 말이죠.
Gosper's Hack이란?
Gosper's Hack(또는 snoob - Same Number Of One Bits)은 현재 정수에서 같은 개수의 1비트를 가진 다음으로 큰 정수를 O(1)에 구하는 알고리즘입니다.
이 알고리즘은 1972년 MIT AI Lab에서 발행한 HAKMEM(AI Memo 239) 문서의 Item 175에 Bill Gosper가 기록했습니다. 원래는 PDP-10 어셈블리 코드로 작성되었으며, 50년이 지난 지금도 경쟁 프로그래밍과 시스템 프로그래밍에서 널리 사용됩니다.
2. 사전 지식
비트 연산 기초
Gosper's Hack을 이해하려면 기본적인 비트 연산에 익숙해야 합니다. 간단히 복습해봅시다.
| 연산자 | 이름 | 설명 | 예시 |
|---|---|---|---|
& |
AND | 둘 다 1일 때만 1 | 1010 & 1100 = 1000 |
| |
OR | 하나라도 1이면 1 | 1010 | 1100 = 1110 |
^ |
XOR | 서로 다르면 1 | 1010 ^ 1100 = 0110 |
~ |
NOT | 비트 반전 | ~1010 = 0101 |
<< |
Left Shift | 왼쪽으로 이동 | 0011 << 2 = 1100 |
>> |
Right Shift | 오른쪽으로 이동 | 1100 >> 2 = 0011 |
2의 보수(Two's Complement)
컴퓨터는 음수를 2의 보수로 표현합니다. 정수 $x$의 음수 $-x$는 다음과 같이 계산됩니다:
$$-x = \sim x + 1$$
예를 들어, 8비트에서 $x = 12$일 때:
x = 00001100
~x = 11110011
-x = 11110100
이 성질이 Gosper's Hack의 핵심입니다.
핵심 비트 트릭
(1) 최하위 1비트 추출: x & -x
$x$와 $-x$를 AND 연산하면 가장 오른쪽에 있는 1비트만 남습니다.
x = 01011000
-x = 10101000
x & -x = 00001000
왜 그럴까요? $-x = \sim x + 1$이므로, $x$의 최하위 1비트 오른쪽은 모두 0이고, NOT 연산 후 1을 더하면 그 위치에서 캐리가 멈춥니다. 따라서 최하위 1비트 위치만 양쪽 모두 1이 됩니다.
(2) 최하위 1비트 제거: x & (x - 1)
x = 01011000
x - 1 = 01010111
x & (x-1) = 01010000
(3) popcount와 ctz
- popcount: 1비트의 개수 (population count)
- ctz: 오른쪽 끝의 연속된 0의 개수 (count trailing zeros)
C++에서는 __builtin_popcount(x), __builtin_ctz(x)로 사용할 수 있습니다.
3. Gosper's Hack 핵심 아이디어
목표
정수 $x$가 주어졌을 때, $x$와 같은 개수의 1비트를 가지면서 $x$보다 큰 가장 작은 정수를 찾는 것입니다.
직관적 이해: 수동 알고리즘
비트열을 직접 조작한다고 생각해봅시다. 예를 들어 0101110 (46)에서 시작합니다.
관찰: 더 큰 수를 만들려면 어떤 1비트가 왼쪽으로 이동해야 합니다. 가장 작은 증가를 원하므로:
- 가장 오른쪽에서, 왼쪽에 0이 있는 1비트를 찾습니다
→ 위 예시에서 인덱스 3의 1비트 (왼쪽이 0) - 그 비트를 왼쪽으로 한 칸 이동
→0110110(54) — 하지만 이건 다음 수가 아닙니다! - 이동한 비트 오른쪽의 나머지 1들을 가장 오른쪽으로 모읍니다
→0110011(51) — 이것이 정답!
정리하면:
원본: 0 1 0 1 1 1 0 (46)
↑ 이 비트를 왼쪽으로
중간: 0 1 1 0 1 1 0 (54)
↓ 나머지 1들을 오른쪽으로
결과: 0 1 1 0 0 1 1 (51)
핵심 통찰
임의의 비트열은 오른쪽 끝에서 다음과 같은 구조를 가집니다:
$$\underbrace{...}_{\text{상위 비트들}} \underbrace{1...1}_{t_1\text{개}} \underbrace{0...0}_{t_0\text{개}}$$
여기서 $t_0 \geq 0$은 trailing zeros의 개수, $t_1 \geq 1$은 그 바로 왼쪽 연속된 1의 개수입니다.
다음 순열을 만들려면:
- 위치 $t_0 + t_1 - 1$의 1비트를 위치 $t_0 + t_1$로 이동 (왼쪽으로 1칸)
- 나머지 $t_1 - 1$개의 1비트를 위치 0부터 배치
4. 알고리즘 상세 분석
전체 코드
C++ 버전
unsigned next_same_popcount(unsigned x) {
unsigned lowest = x & -x; // 1. 최하위 1비트
unsigned ripple = x + lowest; // 2. 캐리 전파
unsigned ones = x ^ ripple; // 3. 변경된 비트들
ones = (ones >> 2) / lowest; // 4. 오른쪽 정렬
return ripple | ones; // 5. 병합
}
Python 버전
def next_same_popcount(x):
lowest = x & -x
ripple = x + lowest
ones = x ^ ripple
ones = (ones >> 2) // lowest
return ripple | ones
한 줄씩 분해
예시로 $x = 46$ (0101110)을 사용합니다.
Step 1: lowest = x & -x
최하위 1비트를 추출합니다.
x = 0101110
-x = 1010010
lowest = 0000010 (= 2)
Step 2: ripple = x + lowest
최하위 1비트를 더하면, 연속된 1비트 블록에 캐리가 전파됩니다.
x = 0101110
lowest = 0000010
ripple = 0110000 (= 48)
이 연산은 연속된 111...0 패턴을 1000...0으로 바꿉니다. 마치 이진수 덧셈에서 캐리가 퍼지는 것처럼요.
Step 3: ones = x ^ ripple
XOR 연산으로 변경된 비트들을 찾습니다.
x = 0101110
ripple = 0110000
ones = 0011110 (= 30)
이 결과는 변경된 모든 비트 위치를 나타냅니다. $t_0 + t_1 + 1$개의 연속된 1비트입니다.
Step 4: ones = (ones >> 2) / lowest
이 단계가 가장 마법 같습니다. 목표는 $t_1 - 1$개의 1비트를 가장 오른쪽으로 보내는 것입니다.
ones = 0011110 (30)
ones >> 2 = 0000111 (7) — 2비트 오른쪽으로 (여분 2개 제거)
lowest = 0000010 (2)
(ones>>2)/lowest = 0000011 (3) — lowest로 나누기 = t_0만큼 추가 shift
왜 >> 2인가요? XOR 결과에는 "원래 위치"와 "새 위치"를 나타내는 2개의 여분 비트가 포함되어 있기 때문입니다.
왜 / lowest인가요? lowest는 $2^{t_0}$이므로, 나누기는 $t_0$비트만큼 오른쪽 시프트와 같습니다.
Step 5: return ripple | ones
상위 비트(ripple)와 하위 비트(ones)를 병합합니다.
ripple = 0110000
ones = 0000011
result = 0110011 (= 51)
시각적 요약
x = 0 1 0 1 1 1 0 (46)
↓ ↓ ↓ ↓
lowest = 0 0 0 0 0 1 0 (2) — 최하위 1비트
↓ ↓ ↓ ↓
ripple = 0 1 1 0 0 0 0 (48) — 캐리 전파 후 상위 부분
↓ ↓ ↓ ↓
ones = 0 0 1 1 1 1 0 (30) — 변경된 비트들
↓ ↓ ↓ ↓
ones = 0 0 0 0 0 1 1 (3) — 시프트 후 하위 부분
↓ ↓ ↓ ↓
result = 0 1 1 0 0 1 1 (51) — 최종 결과
5. 수학적 증명
왜 x & -x가 최하위 1비트를 추출하는가?
2의 보수에서 $-x = \sim x + 1$입니다.
$x$의 비트열을 분석하면:
- 최하위 1비트(위치 $t_0$) 오른쪽: 모두 0
- $\sim x$에서: 위치 $t_0$ 오른쪽은 모두 1
- $\sim x + 1$에서: 캐리가 위치 $t_0$까지 전파되어 그 위치만 1이 됨
따라서 $x$와 $-x$는 정확히 위치 $t_0$에서만 둘 다 1이고, AND 연산 결과는 $2^{t_0}$입니다.
왜 x + lowest가 캐리를 발생시키는가?
$x$의 하위 부분 구조:
$$x = ...b_{t_0+t_1} \underbrace{1...1}_{t_1} \underbrace{0...0}_{t_0}$$
$\text{lowest} = 2^{t_0}$를 더하면:
- 위치 $t_0$의 0이 1이 됨
- 위치 $t_0$부터 $t_0 + t_1 - 1$까지 연속된 1들에 캐리 전파
- 위치 $t_0 + t_1$에 새로운 1이 생김 (여기가 원래 0이었음)
결과:
$$\text{ripple} = ...b_{t_0+t_1}' 1 \underbrace{0...0}_{t_0+t_1}$$
여기서 $b_{t_0+t_1}' = b_{t_0+t_1} + 1$ (캐리 반영).
왜 (ones >> 2) / lowest가 정확히 $(t_1 - 1)$개의 1을 배치하는가?
$\text{ones} = x \oplus \text{ripple}$은 변경된 모든 비트입니다.
변경된 비트:
- 위치 $t_0$부터 $t_0 + t_1$까지 = $t_1 + 1$개의 연속된 1
즉, $\text{ones} = 2^{t_0} \cdot (2^{t_1+1} - 1)$
2비트 오른쪽 시프트:
$$\text{ones} \gg 2 = 2^{t_0-2} \cdot (2^{t_1+1} - 1) = 2^{t_0} \cdot \frac{2^{t_1+1} - 1}{4}$$
(단, $t_0 \geq 2$가 아니어도 비트 연산 특성상 동작)
lowest로 나누기 ($= 2^{t_0}$으로 나누기 = $t_0$비트 시프트):
$$\frac{\text{ones} \gg 2}{\text{lowest}} = \frac{2^{t_1+1} - 1}{4} = 2^{t_1-1} - 1 + \frac{3}{4}$$
정수 나눗셈이므로 $= 2^{t_1-1} - 1$, 이는 $(t_1 - 1)$개의 연속된 1비트입니다.
결과가 "다음 순열"임을 보장하는 이유
- 1비트 개수 보존: ripple에서 1개 증가, ones에서 $t_1 - 1$개 = 원래 $t_1$개와 동일
- 최소 증가: 가장 오른쪽의 이동 가능한 비트를 최소한으로 이동하고, 나머지를 가장 오른쪽에 배치
6. 전체 순회 패턴
조합 순회 템플릿
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5, k = 3;
// 초기값: k개의 1이 오른쪽에 모인 상태
int x = (1 << k) - 1; // 00111
int limit = 1 << n; // 100000
while (x < limit) {
// x를 사용한 작업 수행
cout << bitset<5>(x) << " (" << x << ")" << endl;
// 다음 조합으로 이동 (Gosper's Hack)
int lowest = x & -x;
int ripple = x + lowest;
int ones = ((x ^ ripple) >> 2) / lowest;
x = ripple | ones;
}
return 0;
}
Python
def iterate_combinations(n, k):
x = (1 << k) - 1 # 초기값
limit = 1 << n
while x < limit:
# x를 사용한 작업
print(f"{x:0{n}b} ({x})")
# Gosper's Hack
lowest = x & -x
ripple = x + lowest
ones = ((x ^ ripple) >> 2) // lowest
x = ripple | ones
iterate_combinations(5, 3)
출력
00111 (7)
01011 (11)
01101 (13)
01110 (14)
10011 (19)
10101 (21)
10110 (22)
11001 (25)
11010 (26)
11100 (28)
주의사항
k = 0인 경우
초기값이 0이고, 0 & -0 = 0이므로 무한 루프에 빠집니다. 별도 처리가 필요합니다.
if (k == 0) {
// 공집합 하나만 존재
process(0);
return;
}
k = n인 경우
초기값이 $2^n - 1$이고, 다음 값이 $2^n$을 초과하여 종료됩니다. 정상 동작합니다.
오버플로우 주의
n이 크면 (32 또는 64에 가까우면) 오버플로우가 발생할 수 있습니다. unsigned 또는 unsigned long long을 사용하세요.
7. 최적화 변형
원본의 한계: 나눗셈의 비용
Gosper's Hack의 원본 코드에는 나눗셈 연산이 포함되어 있습니다:
ones = (ones >> 2) / lowest;
lowest가 항상 2의 거듭제곱이므로 이 나눗셈은 사실상 비트 시프트입니다. 하지만 컴파일러는 lowest가 2의 거듭제곱임을 알 수 없어 느린 범용 나눗셈 명령어를 사용합니다.
ctz를 활용한 최적화
__builtin_ctz(x) (count trailing zeros)는 대부분의 현대 CPU에서 단일 명령어로 실행됩니다 (x86의 TZCNT).
unsigned next_same_popcount_fast(unsigned x) {
unsigned t0 = __builtin_ctz(x); // trailing zeros 개수
unsigned lowest = x & -x; // 또는 1u << t0
unsigned ripple = x + lowest;
unsigned ones = (x ^ ripple) >> (t0 + 2); // 나눗셈 대신 시프트!
return ripple | ones;
}
어셈블리 레벨 비교
x & -x는 x86에서 blsi라는 단일 명령어로 컴파일됩니다:
; x & -x
blsi rax, rdi ; 1 instruction!
반면 1 << ctz(x)는:
; 1 << __builtin_ctz(x)
mov eax, 1
tzcnt rcx, rdi
shlx rax, rax, rcx ; 3 instructions
최적화된 전체 함수는 약 7개의 명령어로 컴파일됩니다:
tzcnt rax, rdi ; t0 = ctz(x)
blsi rcx, rdi ; lowest = x & -x
add rcx, rdi ; ripple = x + lowest
xor rdi, rcx ; tmp = x ^ ripple
add al, 2 ; t0 + 2
shrx rax, rdi, rax ; tmp >> (t0 + 2)
or rax, rcx ; ripple | ones
벤치마크
$n = 48$, $k = 8$로 약 3억 7천만 개의 조합을 순회할 때:
| 버전 | 시간 |
|---|---|
| 원본 (나눗셈 사용) | ~2.96초 |
| 단순 구현 (ctz 사용) | ~2.55초 |
| 최적화 버전 | ~1.11초 |
최적화 버전이 원본보다 2.5배 이상 빠릅니다.
8. 시간 복잡도 분석
단일 연산
Gosper's Hack의 각 연산은 O(1)입니다:
- 비트 AND, OR, XOR: O(1)
- 덧셈: O(1)
- 시프트: O(1)
- 나눗셈 (또는 ctz + 시프트): O(1)
전체 순회
n개 중 k개를 선택하는 모든 조합을 순회하면:
$$T(n, k) = O\left(\binom{n}{k}\right)$$
이는 불필요한 검사 없이 정확히 필요한 조합만 순회하므로 최적입니다.
비교: 브루트포스
| 방법 | 시간 복잡도 |
|---|---|
| 0~$2^n$ 순회 + popcount 체크 | $O(2^n)$ |
| Gosper's Hack | $O\binom{n}{k}$ |
예: $n = 30$, $k = 5$일 때
- 브루트포스: $2^{30} \approx 10^9$
- Gosper: $\binom{30}{5} = 142506$
- 약 7000배 차이!
공간 복잡도
O(1) — 상수 개의 변수만 사용합니다.
9. 언제 쓰고, 언제 안 써도 되는가
Gosper's Hack이 빛나는 상황
1. 비트마스크 DP에서 특정 크기 부분집합만 필요할 때
외판원 문제(TSP) 등에서 "정확히 k개 도시를 방문한 상태"만 처리해야 할 때 유용합니다.
// k개 도시를 방문한 모든 상태에 대해
for (int mask = (1 << k) - 1; mask < (1 << n); ) {
// DP 처리
dp[mask] = ...;
// 다음 상태
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
2. 시간 제한이 빡빡한 경쟁 프로그래밍
모든 조합을 빠르게 순회해야 할 때, itertools.combinations보다 빠를 수 있습니다 (언어와 상황에 따라 다름).
3. 비트 인덱스가 직접 필요한 경우
비트마스크 자체로 작업해야 할 때 (배열 인덱스 변환 없이) 효율적입니다.
굳이 필요 없는 상황
1. 가독성이 중요한 실무 코드
# 이게 훨씬 읽기 쉽습니다
from itertools import combinations
for combo in combinations(range(n), k):
process(combo)
2. 조합의 원소 인덱스가 필요할 때
Gosper's Hack은 비트마스크를 주지만, 어떤 비트가 켜져 있는지 알려면 추가 작업이 필요합니다.
3. n이 작을 때
$n \leq 15$ 정도면 브루트포스도 충분히 빠릅니다.
대안 비교
| 방법 | 장점 | 단점 |
|---|---|---|
| Gosper's Hack | O(1) per step, 비트마스크 직접 사용 | 가독성 낮음, 디버깅 어려움 |
itertools.combinations |
가독성 좋음, Pythonic | 비트마스크 변환 필요 |
next_permutation (C++) |
유연함, STL 표준 | 비트 배열 필요 |
| 재귀적 생성 | 이해하기 쉬움 | 함수 호출 오버헤드 |
10. 실전 응용 예제
예제 1: 크기 k인 부분집합 합 계산
문제: 배열에서 정확히 k개 원소를 선택했을 때 가능한 모든 합을 구하라.
#include <bits/stdc++.h>
using namespace std;
set<int> subset_sums(vector<int>& arr, int k) {
int n = arr.size();
set<int> result;
int mask = (1 << k) - 1;
int limit = 1 << n;
while (mask < limit) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += arr[i];
}
}
result.insert(sum);
// Gosper's Hack
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
return result;
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
int k = 3;
auto sums = subset_sums(arr, k);
for (int s : sums) {
cout << s << " ";
}
// 출력: 6 7 8 9 10 11 12
return 0;
}
예제 2: 비트마스크 DP - 최소 비용 할당
문제: n명의 사람에게 n개의 작업을 할당할 때, 정확히 k개 작업이 할당된 상태에서의 최소 비용을 구하라.
// cost[i][j] = i번 사람이 j번 작업을 할 때 비용
int solve(int cost[N][N], int n, int k) {
vector<int> dp(1 << n, INF);
dp[0] = 0;
// 모든 가능한 할당 상태를 순회
for (int mask = 0; mask < (1 << n); mask++) {
int person = __builtin_popcount(mask);
if (person >= n) continue;
for (int job = 0; job < n; job++) {
if (mask & (1 << job)) continue;
int next = mask | (1 << job);
dp[next] = min(dp[next], dp[mask] + cost[person][job]);
}
}
// 정확히 k개 작업이 할당된 상태 중 최소값
int result = INF;
int mask = (1 << k) - 1;
int limit = 1 << n;
while (mask < limit) {
result = min(result, dp[mask]);
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
return result;
}
예제 3: 백준 1182 - 부분수열의 합
문제: N개의 정수로 이루어진 수열에서 크기가 양수인 부분수열 중 합이 S가 되는 경우의 수
Gosper's Hack으로 크기별로 순회하는 풀이:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, s;
cin >> n >> s;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int count = 0;
// 크기 1부터 n까지 모든 부분수열
for (int k = 1; k <= n; k++) {
int mask = (1 << k) - 1;
int limit = 1 << n;
while (mask < limit) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
sum += arr[i];
}
}
if (sum == s) count++;
// Gosper's Hack
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
}
cout << count << endl;
return 0;
}
11. 변형 및 확장
역순 순회: 이전 순열 구하기
다음 큰 수가 아닌 이전 작은 수를 구하는 것도 가능합니다. Hacker's Delight 책에 소개된 방법입니다.
unsigned prev_same_popcount(unsigned x) {
unsigned t = x | (x - 1);
unsigned m = ~t & (t + 1);
unsigned r = t + 1;
return (m - 1) ^ (r & -r);
}
또는 비트를 반전시켜 next를 구한 뒤 다시 반전:
unsigned prev_same_popcount_alt(unsigned x, int n) {
unsigned flipped = ~x & ((1u << n) - 1);
unsigned next_flipped = next_same_popcount(flipped);
return ~next_flipped & ((1u << n) - 1);
}
모든 k에 대해 순회
크기 0부터 n까지 모든 부분집합을 크기순으로 순회하려면:
for (int k = 0; k <= n; k++) {
if (k == 0) {
process(0);
continue;
}
int mask = (1 << k) - 1;
int limit = 1 << n;
while (mask < limit) {
process(mask);
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
}
64비트 초과 처리
n이 64를 넘으면 기본 정수 타입으로는 부족합니다.
방법 1: 큰 정수 라이브러리 사용
Python은 기본적으로 임의 정밀도 정수를 지원하므로 그대로 사용 가능합니다.
def next_same_popcount(x):
lowest = x & -x
ripple = x + lowest
ones = ((x ^ ripple) >> 2) // lowest
return ripple | ones
# n = 100, k = 5도 동작
x = (1 << 5) - 1
limit = 1 << 100
count = 0
while x < limit and count < 10:
print(bin(x))
x = next_same_popcount(x)
count += 1
방법 2: in-place 연산으로 최적화
큰 정수에서는 힙 할당이 병목이 됩니다. GMP 라이브러리의 in-place 함수를 사용하면 10배 이상 빨라질 수 있습니다.
특수 케이스 처리
unsigned next_safe(unsigned x, int n) {
// k = 0: 다음 값 없음
if (x == 0) return 0; // 또는 에러 처리
// 이미 최대값인 경우
if (x >= ((1u << n) - (1u << (n - __builtin_popcount(x))))) {
return 0; // 또는 에러 처리
}
unsigned c = x & -x;
unsigned r = x + c;
return (((r ^ x) >> 2) / c) | r;
}
12. 마무리
핵심 포인트 3줄 요약
- Gosper's Hack은 같은 popcount를 가진 다음 큰 정수를 O(1)에 구합니다
- n개 중 k개 조합을 비트마스크로 순회할 때, $O(2^n)$ 대신 $O(\binom{n}{k})$에 가능
__builtin_ctz를 활용한 최적화 버전이 2배 이상 빠릅니다
코드 템플릿 (복사용)
// C++ 기본 버전
int mask = (1 << k) - 1;
while (mask < (1 << n)) {
// process(mask);
int c = mask & -mask;
int r = mask + c;
mask = (((r ^ mask) >> 2) / c) | r;
}
// C++ 최적화 버전
int mask = (1 << k) - 1;
while (mask < (1 << n)) {
// process(mask);
int t = __builtin_ctz(mask);
int r = mask + (mask & -mask);
mask = r | ((mask ^ r) >> (t + 2));
}
# Python
mask = (1 << k) - 1
while mask < (1 << n):
# process(mask)
c = mask & -mask
r = mask + c
mask = (((mask ^ r) >> 2) // c) | r
참고 자료
- HAKMEM (MIT AI Memo 239, 1972) - Item 175
https://www.inwap.com/pdp10/hbaker/hakmem/hacks.html - Hacker's Delight (Henry S. Warren, 2002/2012) - Chapter 2
비트 조작의 바이블. snoob 함수와 다양한 변형 수록 - HAKMEM Item 175 시각적 설명
https://iamkate.com/code/hakmem-item-175/ - Harvard CS 207 - Bits
https://read.seas.harvard.edu/~kohler/class/cs207-s12/lec12.html
Gosper's Hack은 50년 전 MIT 해커들의 지혜가 담긴 알고리즘입니다. 단 몇 줄의 코드지만, 그 안에는 2의 보수, 캐리 전파, 비트 마스킹의 원리가 녹아 있습니다. 경쟁 프로그래밍에서 시간을 아껴줄 뿐 아니라, 컴퓨터가 숫자를 어떻게 다루는지 이해하는 좋은 창구가 됩니다.
