Count Set Bits Brian Kernighan Algorithm in DSA C

Mental Model

Count how many 1s are in the binary form of a number by removing the rightmost 1 one by one.

Analogy: Imagine you have a row of lit candles (1s). Each time you blow out the rightmost lit candle, you count one until none are left.

Number: 13 (binary 1101)
Bits: 1 -> 1 -> 0 -> 1
Rightmost 1 is at the end here ↑

Dry Run Walkthrough

Input: number = 13 (binary 1101)

Goal: Count how many bits are set to 1 in the number 13

Step 1: Remove rightmost set bit from 1101 (13) using n = n & (n-1)

1101 (13) & 1100 (12) = 1100 (12)

Why: This removes the rightmost 1 bit, reducing the count by one

Step 2: Remove rightmost set bit from 1100 (12)

1100 (12) & 1011 (11) = 1000 (8)

Why: Again remove rightmost 1 bit to count it

Step 3: Remove rightmost set bit from 1000 (8)

1000 (8) & 0111 (7) = 0000 (0)

Why: Last set bit removed, no more 1s left

Result:

Counted 3 set bits in 13 (1101)

Annotated Code

DSA C

#include <stdio.h>

// Function to count set bits using Brian Kernighan's Algorithm
int countSetBits(int n) {
    int count = 0;
    while (n) {
        n = n & (n - 1); // remove rightmost set bit
        count++;
    }
    return count;
}

int main() {
    int number = 13;
    int result = countSetBits(number);
    printf("Number of set bits in %d is %d\n", number, result);
    return 0;
}

while (n) {

loop until all set bits are removed

n = n & (n - 1); // remove rightmost set bit

remove rightmost 1 bit to count it

count++;

increment count for each removed set bit

Output

Number of set bits in 13 is 3

Complexity Analysis

Time: O(k) where k is number of set bits, because each iteration removes one set bit

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Better than checking all bits (O(log n)) because it only loops over set bits, which can be fewer

Edge Cases

number = 0 (no set bits)

loop does not run, count remains 0

DSA C

while (n) {

number = 1 (single set bit)

loop runs once, count becomes 1

DSA C

while (n) {

number with all bits set (e.g., 15 for 4 bits)

loop runs once per set bit, counting all

DSA C

while (n) {

When to Use This Pattern

When asked to count how many bits are 1 in a number efficiently, use Brian Kernighan's algorithm because it quickly removes one set bit per step.

Common Mistakes

Mistake: Looping over all bits by shifting and checking each bit instead of removing set bits
Fix: Use n = n & (n - 1) to remove rightmost set bit directly for faster counting

Summary

Counts the number of 1 bits in a number by repeatedly removing the rightmost set bit.

Use when you need a fast way to count set bits without checking every bit.

The key insight is that n & (n-1) drops the lowest set bit, reducing work to only set bits.