Brian Kernighan’s Algorithm

Brian Kernighan’s Algorithm 정수의 이진 표현에서 ‘1’의 개수, 즉 ‘set bits’ 의 개수를 효율적으로 세는 데 사용되는 알고리즘이다.

Core Idea

정수 n에 대해 다음을 반복한다:

n = n & (n - 1);
count += 1;

• n & (n-1)은 n의 가장 낮은 위치의 1 인 bit 하나를 0 으로 바꿈
• 그 결과 n 에 1 인 bit 가 k 개 있으면 정확히 k 번만 루프를 돌게 됨

Algorithm 의 시간복잡도는 O(k) (k = num of set bits)로, 매 비트(w)마다 도는 단순 방법(O(w))보다 평균적으로 훨씬 빠르다.

그렇기에 sparse bit representation 에서 특히 유용하다.

Commonly Used

check if power of two

1
// n > 0
2
bool is_power_of_two(uint32_t n){
3
    return n && ((n & (n - 1)) == 0);
4
}

1
int count = __builtin_popcountll(x); // for long long
2
int count = __builtin_popcount(x);   // for int
3
int count = __builtin_popcountl(x);  // for long

iterate only for set bits

1
while (n > 0) {
2
    n &= n - 1
3
    // use of n
4
    // lsb = n & -n; -> get lowest set bit
5
 }