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

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Done: count set bits

Yes↓

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

↓

Increment count

↓

Repeat check

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 Java

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 the rightmost set bit each loop.

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	11 != 0, continue
3	Remove rightmost set bit: n = n & (n-1)	00001011 & 00001010	11 & 10 = 10	0	n becomes 10 (binary 1010)
4	Increment count	00001010	10	1	Count incremented to 1
5	Check n != 0	00001010	10	1	10 != 0, continue
6	Remove rightmost set bit: n = n & (n-1)	00001010 & 00001001	10 & 9 = 8	1	n becomes 8 (binary 1000)
7	Increment count	00001000	8	2	Count incremented to 2
8	Check n != 0	00001000	8	2	8 != 0, continue
9	Remove rightmost set bit: n = n & (n-1)	00001000 & 00000111	8 & 7 = 0	2	n becomes 0 (binary 0000)
10	Increment count	00000000	0	3	Count incremented to 3
11	Check n != 0	00000000	0	3	0 == 0, stop loop
12	Return count	-	-	3	Total set bits counted: 3

💡 Loop stops when n becomes 0, meaning no set bits remain.

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 (see steps 3, 6, 9 in execution_table).

Why does the loop stop when n becomes zero?

When n is zero, it means no bits are set to 1 anymore, so the count of set bits is complete (see step 11 in execution_table).

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, count equals the total number of set bits (see steps 4, 7, 10 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the value of n in decimal?

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 loop condition n != 0 become false?

A Step 10

B Step 11

C Step 12

D Step 9

💡 Hint

Look for the step where 'Check n != 0' results in stopping the loop in the execution_table.

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

A 3

B 4

C 5

D 1

💡 Hint

Count increments once per set bit removed; 15 has four set bits (1111).

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 bits set to 1 in O(number of set bits) time.

Full Transcript

This visualization shows how Brian Kernighan's algorithm counts set bits in a number. Starting with the number n, the algorithm checks if n is not zero. If true, it removes the rightmost set bit by performing n = n & (n-1), then increments the count. This repeats until n becomes zero, meaning no set bits remain. The count variable tracks how many set bits were removed, which equals the total number of set bits in the original number. 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 why the loop stops. The quiz tests understanding of the steps and bit counting logic.

Practice

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

easy

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

B. It converts the number to binary string and counts '0's

C. It shifts the bits to the right without changing the number

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

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 D

4. Quick Check:

   Clearing bits one by one counts set bits [OK]

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

Common Mistakes:

• Counting total digits instead of set bits
• Shifting bits without counting
• Counting zeros instead of ones

2. Which of the following Java code snippets correctly implements the Brian Kernighan algorithm to count set bits?

easy

A. int count = 0; for(int i=0; i<32; i++) { if((n & (1 << i)) != 0) count++; }

B. int count = 0; while(n > 0) { n = n >> 1; count++; }

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

D. int count = 0; while(n > 0) { n = n | (n - 1); count++; }

Solution

1. Step 1: Identify the correct bit clearing operation

   The Brian Kernighan algorithm uses n = n & (n - 1) to clear the least significant set bit.

2. Step 2: Verify the loop and count increment

   Loop runs while n > 0 and increments count each time a bit is cleared.

3. Final Answer:

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

4. Quick Check:

   Use n = n & (n - 1) to clear bits [OK]

Hint: Use n = n & (n - 1) inside loop to count bits [OK]

Common Mistakes:

• Using right shift instead of bit clearing
• Using bitwise OR instead of AND
• Counting bits by checking each bit manually

3. What is the output of the following Java code snippet?

int n = 13; // binary 1101
int count = 0;
while (n > 0) {
  n = n & (n - 1);
  count++;
}
System.out.println(count);

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Convert 13 to binary and count set bits

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

2. Step 2: Apply Brian Kernighan algorithm iterations

   Each iteration clears one set bit: - Iteration 1: 1101 & 1100 = 1100 - Iteration 2: 1100 & 1011 = 1000 - Iteration 3: 1000 & 0111 = 0000 Loop runs 3 times, so count = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of set bits in 13 = 3 [OK]

Hint: Count set bits in binary 1101 = 3 [OK]

Common Mistakes:

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

4. Identify the error in the following Java code that attempts to count set bits using Brian Kernighan's algorithm:

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

medium

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

B. Incorrect loop condition should be n > 0

C. Missing initialization of count variable

D. Using bitwise OR instead of AND

Solution

1. Step 1: Check the bit clearing operation

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

2. Step 2: Effect of incorrect operation

   Using n + 1 does not clear the least significant set bit and leads to incorrect counting or infinite loop.

3. Final Answer:

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

4. Quick Check:

   Use n & (n - 1) to clear bits [OK]

Hint: Always use n & (n - 1) to clear bits [OK]

Common Mistakes:

• Using n + 1 instead of n - 1
• Wrong loop condition causing infinite loop
• Confusing AND with OR operators

5. Given an array of integers, which Java method correctly uses Brian Kernighan's algorithm to return the total count of set bits in all elements?

int totalSetBits(int[] arr) {
  int total = 0;
  for (int num : arr) {
    while (num > 0) {
      num = num & (num - 1);
      total++;
    }
  }
  return total;
}

What is the output of totalSetBits(new int[]{3, 5, 7})?

hard

A. 7

B. 6

C. 8

D. 5

Solution

1. Step 1: Count set bits for each element

   3 (binary 11) has 2 set bits, 5 (binary 101) has 2 set bits, 7 (binary 111) has 3 set bits.

2. Step 2: Sum all set bits

   Total = 2 + 2 + 3 = 7.

3. Step 3: Verify code logic

   The code correctly counts set bits for each number and sums them in total.

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Sum of set bits in 3,5,7 = 7 [OK]

Hint: Sum set bits of each number using Brian Kernighan [OK]

Common Mistakes:

• Miscounting set bits in numbers
• Adding counts incorrectly
• Using wrong bit clearing logic