Brian Kernighan's Algorithm

Preface

Brian Kernighan's algorithm is an algorithm for counting the number of set bits (bits with value 1) in a binary integer. The algorithm works by repeatedly performing a bitwise "and" operation between the integer and its predecessor with a single bit shifted to the left until the integer becomes zero. Each time the bitwise "and" operation produces a nonzero result, it means that there is a set bit in the current position, and the algorithm increments a counter.

The advantage of this algorithm over a simple loop that checks each bit in turn is that it only requires a number of iterations equal to the number of set bits in the integer, rather than the number of bits in the integer. This makes it much faster for integers with a small number of set bits.

Implementation

int count_set_bits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

Test case

When n = 9, then 9(1001) AND 8 (1000). Got the result 8(1000)
When = 8, then 8(1000) AND 7 (0111). Got the result 0 (0000)

When n = 13, then 13(1101) AND 12(1100). Got the result 12(1100)
When n = 12, then 12(1100) AND 11(1011). Got the result 8(1000)
When = 8, then 8(1000) AND 7 (0111). Got the result 0 (0000)

Analysis

Time Complexity: $O(logN)$
Space Complexity: $O(1)$