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→Stop, count is final

Yes↓

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

↓

Increment count

↩Back to Check if n != 0?

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

Execution Sample

DSA C++

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

This code counts how many bits are set to 1 in the binary form of n using Brian Kernighan's method.

Execution Table

Step	Operation	n (binary)	n (decimal)	Count	Visual State
1	Start	00001011	11	0	Initial number 11 (binary 1011)
2	Check n != 0	00001011	11	0	n is not zero, continue
3	Remove rightmost set bit: n = n & (n-1)	00001011 & 00001010	11 & 10 = 10	0	Rightmost set bit removed, n=10 (1010)
4	Increment count	00001010	10	1	Count incremented to 1
5	Check n != 0	00001010	10	1	n is not zero, continue
6	Remove rightmost set bit: n = n & (n-1)	00001010 & 00001001	10 & 9 = 8	1	Rightmost set bit removed, n=8 (1000)
7	Increment count	00001000	8	2	Count incremented to 2
8	Check n != 0	00001000	8	2	n is not zero, continue
9	Remove rightmost set bit: n = n & (n-1)	00001000 & 00000111	8 & 7 = 0	2	Rightmost set bit removed, n=0 (0000)
10	Increment count	00000000	0	3	Count incremented to 3
11	Check n != 0	00000000	0	3	n is zero, stop
12	Return count	-	-	3	Total set bits counted: 3

💡 n becomes 0 at step 11, loop ends, count is 3

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
n (decimal)	11	10	8	0	0
n (binary)	00001011	00001010	00001000	00000000	00000000
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 set bits by one each time, as shown in steps 3, 6, and 9 in the execution_table.

Why does the loop stop when n becomes zero?

When n is zero, it means no set bits remain. The condition n != 0 fails at step 11, so the loop ends and the count is final.

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

Each time the rightmost set bit is removed, count increments by 1 (steps 4, 7, 10), so count equals the total number of set bits after the loop.

Visual Quiz - 3 Questions

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

A 8

B 9

C 10

D 7

💡 Hint

Check the 'n (decimal)' column at step 6 in the execution_table.

At which step does the condition n != 0 become false?

A Step 10

B Step 11

C Step 12

D Step 9

💡 Hint

Look at the 'Operation' and 'n (decimal)' columns around step 11 in the execution_table.

If the initial number n was 15 (binary 1111), how many times would the loop run?

A 3

B 4

C 5

D 1

💡 Hint

Count the number of set bits in 15 (1111) and relate to how many times count increments in the execution_table.

Concept Snapshot

Count Set Bits using Brian Kernighan 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 clearing one bit per iteration.

Full Transcript

This visualization traces the Brian Kernighan algorithm for counting set bits in an integer. Starting with n=11 (binary 1011), the algorithm repeatedly removes the rightmost set bit by computing n = n & (n-1). Each removal increments the count. The loop continues until n becomes zero, indicating no set bits remain. The execution table shows each step's n value in binary and decimal, the count, and the operation performed. The variable tracker highlights how n and count change after each removal. Key moments clarify why the bit removal works, why the loop stops, and how count relates to set bits. The quiz tests understanding of n's value at specific steps, loop termination, and behavior with different inputs. The snapshot summarizes the algorithm's core steps and efficiency.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in an integer?

easy

A. It repeatedly clears the least significant set bit until the number becomes zero.

B. It counts the total number of digits in the integer.

C. It shifts the bits to the right one by one and counts all bits.

D. It converts the number to a string and counts '1' characters.

Solution

1. Step 1: Understand the algorithm's main operation

   The Brian Kernighan algorithm works by clearing the least significant set bit in each iteration.

2. Step 2: Effect of clearing bits

   Each clearing reduces the number of set bits by one until the number becomes zero.

3. Final Answer:

   It repeatedly clears the least significant set bit until the number becomes zero. -> Option A

4. Quick Check:

   Clearing bits one by one counts set bits [OK]

Hint: Clear least significant set bit repeatedly to count bits [OK]

Common Mistakes:

• Counting all bits instead of only set bits
• Using string conversion unnecessarily
• Shifting bits without checking if set

2. Which of the following is the correct syntax for the main loop in Brian Kernighan's algorithm in C++?

easy

A. while (n > 0) { count += n % 2; n /= 2; }

B. for (int i = 0; i < n; i++) { count += n & 1; n >>= 1; }

C. while (n != 0) { n = n & (n - 1); count++; }

D. for (int i = 0; i < 32; i++) { count += (n >> i) & 1; }

Solution

1. Step 1: Identify Brian Kernighan's loop

   The algorithm uses while (n != 0) and clears the least significant set bit by n = n & (n - 1).

2. Step 2: Confirm increment of count

   Each iteration increments count by one for each cleared set bit.

3. Final Answer:

   while (n != 0) { n = n & (n - 1); count++; } -> Option C

4. Quick Check:

   Loop clears bits and counts [OK]

Hint: Use while with n = n & (n-1) to clear bits [OK]

Common Mistakes:

• Using for loop instead of while
• Counting bits by shifting instead of clearing
• Using modulo instead of bitwise operations

3. What is the output of the following C++ code snippet using Brian Kernighan's algorithm?

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

int main() {
  int x = 13;
  std::cout << countSetBits(x);
  return 0;
}

medium

A. 5

B. 3

C. 2

D. 4

Solution

1. Step 1: Convert 13 to binary

   13 in binary is 1101, which has three set bits (1s).

2. Step 2: Apply Brian Kernighan's algorithm

   Each iteration clears one set bit, so count increments 3 times before n becomes 0.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of 1s in 1101 = 3 [OK]

Hint: Count 1s in binary of number for quick answer [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary 1s
• Confusing bitwise AND with OR

4. Identify the error in this Brian Kernighan algorithm implementation:

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

medium

A. Missing return statement.

B. Not initializing count to zero.

C. Using while (n > 0) instead of while (n != 0).

D. Using n + 1 instead of n - 1 in bit clearing step.

Solution

1. Step 1: Check bit clearing operation

   The correct operation to clear the least significant set bit is n = n & (n - 1), not n + 1.

2. Step 2: Effect of wrong operation

   Using n + 1 does not clear bits properly and causes incorrect count or infinite loop.

3. Final Answer:

   Using n + 1 instead of n - 1 in bit clearing step. -> Option D

4. Quick Check:

   Correct bit clearing uses n & (n - 1) [OK]

Hint: Use n & (n - 1) to clear bits, not n + 1 [OK]

Common Mistakes:

• Replacing n - 1 with n + 1
• Confusing loop condition syntax
• Forgetting to increment count

5. Given an array of integers, how can you use Brian Kernighan's algorithm to find the total number of set bits in all elements? Choose the best approach.

hard

A. Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts.

B. Convert all integers to strings and count '1's in each string, then sum.

C. Use a single Brian Kernighan's algorithm call on the sum of all integers.

D. Count set bits only in the first element and multiply by array size.

Solution

1. Step 1: Understand counting set bits per element

   Brian Kernighan's algorithm counts set bits in one integer at a time.

2. Step 2: Apply algorithm to each array element

   Iterate through the array, count set bits for each element, and sum these counts for total.

3. Final Answer:

   Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts. -> Option A

4. Quick Check:

   Sum of individual counts gives total set bits [OK]

Hint: Count bits per element, then sum for total [OK]

Common Mistakes:

• Counting bits of sum instead of each element
• Using string conversion unnecessarily
• Assuming uniform bit count per element