Count Set Bits Brian Kernighan Algorithm in DSA Javascript - 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 JavaScript code that counts the number of set bits (1s) in the binary representation of a number using Brian Kernighan's algorithm?

DSA Javascript

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

console.log(countSetBits(29));

A 3

B 4

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 the rightmost set bit in each iteration, so the loop runs 4 times.

❓ Predict Output

intermediate

Result of Counting Set Bits for Zero

What will be the output of the following code when counting set bits of 0 using Brian Kernighan's algorithm?

DSA Javascript

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

console.log(countSetBits(0));

A 0

B 1

C undefined

D Error

💡 Hint

Zero has no set bits in its binary form.

Since 0 has no bits set to 1, the loop never runs and the count remains 0.

🔧 Debug

advanced

Identify the Error in Brian Kernighan's Algorithm Implementation

What error will the following code produce when trying to count set bits of a positive integer?

DSA Javascript

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

console.log(countSetBits(15));

A Logic error due to operator precedence

B Correct output 4

C TypeError: invalid operation

D Infinite loop

💡 Hint

Check how the bitwise AND and subtraction operators are grouped.

The expression n & n - 1 is interpreted as (n & n) - 1 due to operator precedence, which is not the intended operation. It causes a logic error.

❓ Predict Output

advanced

Output of Counting Set Bits for a Large Number

What is the output of the following code counting set bits of 1023 using Brian Kernighan's algorithm?

DSA Javascript

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

console.log(countSetBits(1023));

A 11

B 9

C 8

D 10

💡 Hint

1023 is one less than 1024, which is 2^10.

1023 in binary is 1111111111 (ten 1s), so the count of set bits is 10.

🧠 Conceptual

expert

Why Brian Kernighan's Algorithm is Efficient for Counting Set Bits

Why is Brian Kernighan's algorithm more efficient than checking each bit individually when counting set bits in an integer?

A It converts the number to a string and counts '1's

B It uses recursion to speed up counting

C It reduces the number of iterations to the number of set bits instead of total bits

D It uses a lookup table for all possible bit patterns

💡 Hint

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

Brian Kernighan's algorithm loops only as many times as there are set bits, skipping zero bits, 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 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