Count Set Bits Brian Kernighan Algorithm in DSA C - Execution Trace

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Done, return count

Yes↓

Remove rightmost set bit: n = n & (n-1)

↓

Increment count

↩Back to Check n != 0

The algorithm repeatedly removes the rightmost set bit from the number and counts how many times this happens until the number becomes zero.

Execution Sample

DSA C

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

Counts how many bits are set to 1 in the binary form of n by removing one set bit at a time.

Execution Table

Step	Operation	n (binary)	n (decimal)	Count	Visual State
1	Start	00001011	11	0	Initial number 11 (binary 1011)
2	Remove rightmost set bit: n = n & (n-1)	00001010	10	1	Removed rightmost set bit from 1011 to 1010
3	Remove rightmost set bit: n = n & (n-1)	00001000	8	2	Removed rightmost set bit from 1010 to 1000
4	Remove rightmost set bit: n = n & (n-1)	00000000	0	3	Removed rightmost set bit from 1000 to 0000
5	Check n != 0	00000000	0	3	n is zero, stop loop

💡 n becomes 0 at step 5, loop ends with count = 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
n (decimal)	11	10	8	0	0
count	0	1	2	3	3

Key Moments - 3 Insights

Why does the algorithm use n = n & (n-1) to remove the rightmost set bit?

Because n & (n-1) clears the rightmost set bit in n, reducing the number of set bits by one each time, as shown in execution_table steps 2 to 4.

Why does the loop stop when n becomes zero?

When n is zero, there are no set bits left to count, so the loop ends as shown in execution_table step 5.

How does the count variable relate to the number of set bits?

Count increments each time a set bit is removed, so at the end it equals the total number of set bits, as tracked in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of n (decimal) after step 3?

A 10

B 8

C 0

D 11

💡 Hint

Check the 'n (decimal)' column in execution_table row for step 3

At which step does the count variable become 2?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Count' column in execution_table and variable_tracker after each step

If the input number n was 8 instead of 11, how many steps would the loop run before stopping?

A 1

B 2

C 3

D 4

💡 Hint

8 in binary is 1000, which has only one set bit; check how many times the loop removes set bits

Concept Snapshot

Count Set Bits using Brian Kernighan's Algorithm:
- Initialize count = 0
- While n != 0:
  - n = n & (n-1) removes rightmost set bit
  - Increment count
- Return count as total set bits
Efficiently counts set bits by skipping zeros.

Full Transcript

This visualization shows how Brian Kernighan's algorithm counts the number of set bits in an integer. Starting with the number n, the algorithm repeatedly removes the rightmost set bit by performing n = n & (n-1). Each removal increments a count. The process continues until n becomes zero, meaning no set bits remain. The execution table traces each step with the binary and decimal values of n, the count, and the visual state of the number. The variable tracker shows how n and count change after each operation. Key moments clarify why the bit removal works and why the loop stops. The quiz tests understanding of the steps and variable values. This method is efficient because it only loops as many times as there are set bits, not the total number of bits.