Count Set Bits in an Integer (Brian Kernighan’s Algorithm)

Counting the number of set bits (1s) in an integer's binary representation is a common task. While you can check every bit, Brian Kernighan’s Algorithm provides a much faster way by only iterating over the set bits.

The Concept

The core trick is the expression n & (n - 1). As we saw in our 'Power of Two' article, this operation always clears the rightmost set bit of a number.

Algorithm

1. Initialize a count variable to 0.
2. While the number n is greater than 0:
   • Perform n = n & (n - 1). This clears the rightmost set bit.
   • Increment count by 1.
3. The loop ends when all bits are cleared (n becomes 0).

Python Implementation

def count_set_bits(n):
    count = 0
    while n > 0:
        n = n & (n - 1)
        count += 1
    return count

# Test: n = 12 (1100 in binary)
print(count_set_bits(12)) # Output: 2

Complexity

• Time Complexity: O(log N) in worst case, but specifically O(K) where K is the number of set bits.
• Space Complexity: O(1).