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

Concept Flow - Count Set Bits Brian Kernighan Algorithm

Start with number n

↓

Check if n != 0?

No→End: count is final

Yes↓

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

↓

Increment count

↩Back to 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 Typescript

function countSetBits(n: number): number {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1);
    count++;
  }
  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	Number (binary)	Number (decimal)	Count	Pointer Changes	Visual State
1	Start	00001011	11	0	n=11	11 (1011)
2	Check n != 0	00001011	11	0	Condition True	11 (1011)
3	Remove rightmost set bit: n = n & (n-1)	00001011 & 00001010	11 & 10 = 10	0	n=10	10 (1010)
4	Increment count	00001010	10	1	count=1	10 (1010)
5	Check n != 0	00001010	10	1	Condition True	10 (1010)
6	Remove rightmost set bit: n = n & (n-1)	00001010 & 00001001	10 & 9 = 8	1	n=8	8 (1000)
7	Increment count	00001000	8	2	count=2	8 (1000)
8	Check n != 0	00001000	8	2	Condition True	8 (1000)
9	Remove rightmost set bit: n = n & (n-1)	00001000 & 00000111	8 & 7 = 0	2	n=0	0 (0000)
10	Increment count	00000000	0	3	count=3	0 (0000)
11	Check n != 0	00000000	0	3	Condition False	0 (0000)
12	End	00000000	0	3	-	Final count = 3

💡 n becomes 0, condition n != 0 is false, loop ends

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
n	11 (1011)	10 (1010)	8 (1000)	0 (0000)	0 (0000)
count	0	1	2	3	3

Key Moments - 3 Insights

Why do we 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. See execution_table steps 3, 6, and 9 where n changes.

Why does the loop stop when n becomes zero?

Because zero has no set bits left, so the condition n != 0 becomes false, ending the loop as shown in execution_table step 11.

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

Each time we remove a set bit, we increment count. When the loop ends, count equals the total number of set bits, as shown in variable_tracker and execution_table final step.

Visual Quiz - 3 Questions

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

A 0 (0000)

B 8 (1000)

C 10 (1010)

D 11 (1011)

💡 Hint

Check the 'Number (decimal)' and 'Number (binary)' columns at step 6 in execution_table.

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

A Step 12

B Step 10

C Step 11

D Step 9

💡 Hint

Look at the 'Operation' and 'Condition' columns in execution_table around steps 10-12.

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

A 4

B 3

C 5

D 1

💡 Hint

Count the number of set bits in 15 (binary 1111) and 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 as total set bits
Efficiently counts 1-bits by clearing one bit per iteration.

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), increments the count, and repeats. The steps continue until n becomes zero. Each removal corresponds to one set bit counted. The variable tracker shows how n and count change after each removal. Key moments clarify why n & (n-1) removes the rightmost set bit, why the loop stops at zero, and how count reflects the total set bits. The quiz tests understanding of these steps and the algorithm's behavior with different inputs.

Practice

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

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 number.

C. It shifts the number to the right until it becomes zero without checking bits.

D. It adds all bits of the number without any bitwise operation.

Solution

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

   The Brian Kernighan algorithm clears the least significant set bit in each iteration by doing n = n & (n-1).

2. Step 2: Effect of clearing bits

   Each clearing reduces the number of set bits by one until the number becomes zero, counting how many set bits were present.

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 set bit repeatedly to count set bits [OK]

Common Mistakes:

• Confusing bit count with digit count
• Using simple right shifts without bit checks
• Ignoring bitwise AND operation

2. Which of the following is the correct TypeScript syntax to clear the least significant set bit of a number n?

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 bitwise operation to clear least set bit

   The operation n = n & (n - 1) clears the least significant set bit in n.

2. Step 2: Verify other options

   OR, XOR, and addition do not clear the least significant set bit correctly.

3. Final Answer:

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

4. Quick Check:

   AND with (n-1) clears least set bit [OK]

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

Common Mistakes:

• Using OR or XOR instead of AND
• Adding numbers instead of bitwise operations
• Missing parentheses around (n - 1)

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

function countSetBits(n: number): number {
  let count = 0;
  while (n > 0) {
    n = n & (n - 1);
    count++;
  }
  return count;
}

console.log(countSetBits(13));

medium

A. 3

B. 4

C. 2

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 steps

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

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Number of 1s in 1101 = 3 [OK]

Hint: Count 1s in binary using n & (n-1) loop [OK]

Common Mistakes:

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

4. Identify the error in this TypeScript function that tries to count set bits using Brian Kernighan's algorithm:

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

medium

A. Return statement is missing.

B. Using != instead of > in the while condition.

C. Incorrect initialization of count variable.

D. Missing parentheses around (n - 1) in the expression.

Solution

1. Step 1: Analyze the expression inside the loop

   The expression n = n & n - 1 lacks parentheses, so it is evaluated as (n & n) - 1, which is incorrect.

2. Step 2: Correct expression

   It should be n = n & (n - 1) to correctly clear the least significant set bit.

3. Final Answer:

   Missing parentheses around (n - 1) in the expression. -> Option D

4. Quick Check:

   Parentheses ensure correct order of operations [OK]

Hint: Use parentheses: n = n & (n - 1) [OK]

Common Mistakes:

• Using != 0 causing potential infinite loop for negatives
• Assuming both conditions always equivalent
• Operator precedence confusion causing wrong calculation

5. Given an array of numbers [5, 7, 10], which TypeScript code correctly uses Brian Kernighan's algorithm to return an array of their set bit counts?

hard

A. const counts = arr.map(n => {
let count = 0;
while (n > 0) {
n = n >> 1;
count++;
}
return count;
});

B. const counts = arr.map(n => n.toString(2).length);

C. const counts = arr.map(n => {
let count = 0;
while (n > 0) {
n = n & (n - 1);
count++;
}
return count;
});

D. const counts = arr.map(n => {
let count = 0;
for (let i = 0; i < 32; i++) {
if ((n & (1 << i)) !== 0) count++;
}
return count;
});

Solution

1. Step 1: Understand Brian Kernighan's algorithm usage

   const counts = arr.map(n => { let count = 0; while (n > 0) { n = n & (n - 1); count++; } return count; }); uses the correct loop with n = n & (n - 1) to count set bits for each number.

2. Step 2: Check other options for correctness

   const counts = arr.map(n => n.toString(2).length); counts total binary digits, not set bits. const counts = arr.map(n => { let count = 0; while (n > 0) { n = n >> 1; count++; } return count; }); counts total bits by shifting, not set bits. const counts = arr.map(n => { let count = 0; for (let i = 0; i < 32; i++) { if ((n & (1 << i)) !== 0) count++; } return count; }); uses a loop checking each bit, which works but is not Brian Kernighan's algorithm.

3. Final Answer:

   const counts = arr.map(n => { let count = 0; while (n > 0) { n = n & (n - 1); count++; } return count; }); -> Option C

4. Quick Check:

   Use n & (n-1) loop inside map for set bits [OK]

Hint: Use map with n & (n-1) loop for each number [OK]

Common Mistakes:

• Counting binary string length instead of set bits
• Using right shift without bit check
• Confusing bitwise loop with simple iteration