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

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→Done

Yes↓

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

↓

Increment count

↓

Repeat 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 Javascript

function countSetBits(n) {
  let 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 repeatedly.

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 4	After Step 7	After Step 10	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 subtracting 1 flips all bits after the rightmost set bit, and ANDing with n clears that rightmost set bit. This is shown in steps 3, 6, and 9 where n changes by removing one set bit each time.

Why does the loop stop when n becomes zero?

When n is zero, it means there are no set bits left to count. The check at steps 2, 5, 8, and 11 ensures the loop continues only while n is not zero.

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

Each time the rightmost set bit is removed (steps 4, 7, 10), count is incremented by one, so at the end (step 12) count equals the total number of set bits.

Visual Quiz - 3 Questions

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

A 9

B 8

C 10

D 0

💡 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 11

B Step 9

C Step 12

D Step 10

💡 Hint

Look at the 'Check n != 0' operations and see when n equals zero.

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

A 3

B 5

C 4

D 1

💡 Hint

Count increments once per set bit removed; 15 has four 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
This counts set bits efficiently by skipping zeros.

Full Transcript

This visualization shows how Brian Kernighan's algorithm counts set bits in a number. Starting with n=11 (binary 1011), the algorithm checks if n is not zero. It then removes the rightmost set bit by computing n = n & (n-1), which clears one set bit each time. After each removal, the count increments by one. This repeats until n becomes zero, meaning no set bits remain. The final count is the total number of set bits. The execution table traces each step, showing n in binary and decimal, the count, and the operation performed. Key moments clarify why the bit removal works and why the loop stops. The quiz tests understanding of the steps and the count increments. This method is efficient because it only loops as many times as there are set bits, not the total number of bits.

Practice

1. What does the Brian Kernighan algorithm do when counting set bits in a number?

easy

A. It converts the number to a string and counts characters

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

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

D. It shifts the number to the right and counts zeros

Solution

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

   The algorithm clears the least significant set bit by doing n = n & (n-1) repeatedly.

2. Step 2: Effect of clearing bits

   Each operation removes one set bit, counting how many times this happens gives the total set bits.

3. Final Answer:

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

4. Quick Check:

   Clearing bits counts set bits [OK]

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

Common Mistakes:

• Counting total digits instead of set bits
• Counting zeros instead of ones
• Using string length instead of bit operations

2. Which of the following is the correct syntax to clear the least significant set bit in JavaScript using Brian Kernighan's method?

easy

A. n = n | (n - 1);

B. n = n & (n - 1);

C. n = n & (n + 1);

D. n = n ^ (n - 1);

Solution

1. Step 1: Identify the bit clearing operation

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

2. Step 2: Verify other options

   Other options do not clear the least significant set bit correctly.

3. Final Answer:

   n = n & (n - 1); -> Option B

4. Quick Check:

   Use AND with (n-1) to clear bit [OK]

Hint: Use n & (n-1) to clear least set bit [OK]

Common Mistakes:

• Using OR or XOR instead of AND
• Adding instead of subtracting 1
• Confusing bitwise operators

3. What is the output of the following JavaScript code?

function countSetBits(n) {
  let count = 0;
  while (n > 0) {
    n = n & (n - 1);
    count++;
  }
  return count;
}
console.log(countSetBits(13));

medium

A. 3

B. 2

C. 4

D. 5

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 loop clears one set bit, so count increments 3 times before n becomes 0.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   13 (1101) has 3 set bits [OK]

Hint: Count set bits by clearing one bit each loop [OK]

Common Mistakes:

• Counting total bits instead of set bits
• Miscounting binary representation
• Off-by-one errors in loop

4. Identify the error in the following code snippet that uses Brian Kernighan's algorithm:

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

medium

A. Not initializing count to 1

B. Using while loop instead of for loop

C. Missing return statement

D. Using n & (n + 1) instead of n & (n - 1)

Solution

1. Step 1: Check the bit clearing operation

   The code uses n = n & (n + 1), which does not clear the least significant set bit correctly.

2. Step 2: Correct operation

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

3. Final Answer:

   Using n & (n + 1) instead of n & (n - 1) -> Option D

4. Quick Check:

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

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

Common Mistakes:

• Using n & (n + 1) which is incorrect
• Confusing loop types
• Forgetting to return count

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

const arr = [3, 5, 7];
// Choose the correct code to count all set bits

A) let total = 0;
for(let n of arr) {
  while(n > 0) {
    n = n & (n - 1);
    total++;
  }
}
console.log(total);

B) let total = 0;
for(let n of arr) {
  total += n.toString(2).length;
}
console.log(total);

C) let total = 0;
for(let n of arr) {
  while(n > 0) {
    n = n | (n - 1);
    total++;
  }
}
console.log(total);

D) let total = 0;
for(let n of arr) {
  total += n & (n - 1);
}
console.log(total);

hard

A. Correctly counts set bits using Brian Kernighan's method

B. Counts total binary digits, not set bits

C. Uses OR instead of AND, incorrect bit clearing

D. Adds bitwise AND result directly, incorrect counting

Solution

1. Step 1: Identify the correct implementation

   The implementation using while(n > 0) { n = n & (n - 1); total++; } correctly applies Brian Kernighan's algorithm by clearing the least significant set bit repeatedly for each array element and incrementing the total count each time.

2. Step 2: Eliminate incorrect options

   The option using n.toString(2).length counts all bits including zeros; using n | (n - 1) does not clear set bits correctly; adding n & (n - 1) directly does not count the number of set bits.

3. Final Answer:

   Correctly counts set bits using Brian Kernighan's method -> Option A

4. Quick Check:

   Clear bits and count in loop [OK]

Hint: Loop clearing bits per number to sum counts [OK]

Common Mistakes:

• Counting total binary length instead of set bits
• Using OR instead of AND for clearing bits
• Adding bitwise results instead of counts