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

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Stop

Yes↓

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

↓

Increment count

↓

Repeat check

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

Execution Sample

DSA Python

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

Counts how many 1-bits are in the binary form of n by removing the rightmost set bit each loop.

Execution Table

Step	Operation	n (binary)	n (decimal)	Count	Visual State
1	Start	1101	13	0	1101 (13)
2	Remove rightmost set bit: n = n & (n-1)	1100	12	1	1100 (12)
3	Remove rightmost set bit: n = n & (n-1)	1000	8	2	1000 (8)
4	Remove rightmost set bit: n = n & (n-1)	0000	0	3	0000 (0)
5	Check n != 0	0000	0	3	Stop: n is zero

💡 n becomes 0 at step 4, loop ends

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
n (decimal)	13	12	8	0	0
n (binary)	1101	1100	1000	0000	0000
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 lowest set bit in n, reducing the number of 1s 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 condition n != 0 fails and the loop ends, as seen in execution_table step 5.

What happens if the input number is zero at the start?

The loop never runs because n != 0 is false initially, so count remains zero, meaning zero set bits.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of count after step 3?

A 1

B 3

C 2

D 0

💡 Hint

Check the 'count' column in execution_table row for step 3.

At which step does n become zero, causing the loop to stop?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'n (decimal)' column and find when it reaches 0.

If the input n was 8 (1000 in binary), how many times would the loop run?

A 1

B 2

C 3

D 4

💡 Hint

Count the number of set bits in 1000 binary; relate to count increments in variable_tracker.

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
Efficiently counts 1-bits by clearing them one by one.

Full Transcript

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