GCC/Clang이 제공하는 비트 연산 내장 함수(builtin)들이다. 대부분 하드웨어 명령어(popcnt, lzcnt, tzcnt 등)로 컴파일되어 O(1)에 동작한다.
각 함수는 unsigned int용이 기본이고, l 접미사는 unsigned long, ll 접미사는 unsigned long long용이다. (예: __builtin_clz, __builtin_clzl, __builtin_clzll) signed 타입을 넘겨도 동작하지만, 이 함수들은 숫자의 값이 아니라 메모리에 저장된 비트 패턴 자체를 다루기 때문에 양수/음수 개념 없이 그냥 0과 1의 나열로 처리한다. 예를 들어 -1은 모든 비트가 1이므로 __builtin_popcount(-1)은 32를 반환한다.
비트 카운팅
__builtin_popcount(x): x의 이진 표현에서 1인 비트의 개수를 반환한다.
__builtin_popcount(13) // 13 = 1101₂ → 3__builtin_popcount(0) // → 0__builtin_parity(x): 1인 비트의 개수가 홀수면 1, 짝수면 0을 반환한다.popcount(x) % 2와 같다.
__builtin_parity(13) // 1이 3개 (홀수) → 1__builtin_parity(12) // 12 = 1100₂, 1이 2개 (짝수) → 0선행/후행 0 카운팅
__builtin_clz(x): Count Leading Zeros. MSB(최상위 비트)부터 연속된 0의 개수를 반환한다. x가 0이면 정의되지 않는다.
__builtin_clz(8) // 8 = 00...01000₂ → 28 (32비트 기준)__builtin_clzll(8) // → 60 (64비트 기준)최상위 비트 위치를 구하거나, x 이하의 가장 큰 2의 제곱수를 구할 때 쓴다.
int msb_pos = 31 - __builtin_clz(x); // x의 최상위 비트 위치long long p = 1LL << (63 - __builtin_clzll(x)); // x 이하의 가장 큰 2의 제곱수__builtin_ctz(x): Count Trailing Zeros. LSB(최하위 비트)부터 연속된 0의 개수를 반환한다. x가 0이면 정의되지 않는다.
__builtin_ctz(12) // 12 = 1100₂ → 2__builtin_ctz(8) // 8 = 1000₂ → 3최하위 set 비트의 위치와 같다. x & -x로 구한 lowest bit의 위치를 바로 알 수 있다.
선행/후행 1 카운팅
__builtin_clo(x): Count Leading Ones. MSB부터 연속된 1의 개수.__builtin_cto(x): Count Trailing Ones. LSB부터 연속된 1의 개수.
이 두 함수는 GCC에서만 지원하고 Clang에서는 지원하지 않는 경우가 있어서, PS에서는 __builtin_clz(~x), __builtin_ctz(~x)로 대체하는 편이 안전하다.
기타
__builtin_ffs(x): Find First Set. 최하위 set 비트의 위치를 1부터 세서 반환한다. x가 0이면 0을 반환한다.
__builtin_ffs(12) // 12 = 1100₂, 최하위 set 비트는 3번째 → 3__builtin_ffs(0) // → 0ctz와 비슷하지만, ffs는 1-indexed이고 x=0일 때 안전하다는 차이가 있다. x != 0일 때 __builtin_ffs(x) == __builtin_ctz(x) + 1이다.
참고