Count Set Bits Brian Kernighan Algorithm in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Brian Kernighan's Algorithm for Counting Set Bits

What is the output of the following TypeScript code that counts the number of set bits (1s) in the binary representation of a number using Brian Kernighan's algorithm?

DSA Typescript

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

console.log(countSetBits(29));

A 4

B 3

C 5

D 2

💡 Hint

Count how many times the loop runs by removing the rightmost set bit each time.

The number 29 in binary is 11101, which has 4 set bits. Brian Kernighan's algorithm removes one set bit per iteration, so the loop runs 4 times.

🧠 Conceptual

intermediate

Understanding the Core Operation in Brian Kernighan's Algorithm

In Brian Kernighan's algorithm, what does the operation n = n & (n - 1) do to the binary representation of n?

A It shifts all bits of <code>n</code> to the left by one.

B It sets the rightmost unset bit (0) in <code>n</code> to 1.

C It flips all bits of <code>n</code>.

D It clears the rightmost set bit (1) in <code>n</code>.

💡 Hint

Think about how subtracting 1 affects the rightmost set bit.

The expression n & (n - 1) removes the rightmost set bit from n. This is the key step in Brian Kernighan's algorithm to count set bits efficiently.

🔧 Debug

advanced

Identify the Error in the Brian Kernighan's Algorithm Implementation

What error will the following TypeScript code produce when trying to count set bits using Brian Kernighan's algorithm?

DSA Typescript

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

console.log(countSetBits(2));

A Returns 0 immediately.

B Returns 4 correctly.

C The code runs infinitely (infinite loop).

D Throws a TypeError at runtime.

💡 Hint

Check the operation inside the loop and how it affects the value of n.

The code uses n & (n + 1) instead of n & (n - 1). This does not clear the rightmost set bit and can cause an infinite loop because n may never become zero.

❓ Predict Output

advanced

Output of Counting Set Bits for Large Number

What is the output of the following TypeScript code that counts set bits using Brian Kernighan's algorithm for the number 1023?

DSA Typescript

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

console.log(countSetBits(1023));

A 11

B 10

C 9

D 8

💡 Hint

Convert 1023 to binary and count the 1s.

1023 in binary is 1111111111 (ten 1s). The algorithm counts all set bits, so the output is 10.

🧠 Conceptual

expert

Why is Brian Kernighan's Algorithm More Efficient Than Checking Each Bit?

Why does Brian Kernighan's algorithm run faster than a simple loop checking each bit of a number to count set bits?

A Because it only loops as many times as there are set bits, not total bits.

B Because it uses recursion instead of iteration.

C Because it converts the number to a string and counts characters.

D Because it uses bit shifting to check every bit one by one.

💡 Hint

Think about how many times the loop runs compared to the number of bits in the number.

Brian Kernighan's algorithm reduces the number of iterations to the count of set bits by clearing one set bit each loop, making it faster especially for numbers with few set bits.

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