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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Brian Kernighan's Set Bits Count

What is the output of the following C++ code that counts set bits using Brian Kernighan's algorithm?

DSA C++

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

int main() {
    int x = 29; // binary 11101
    std::cout << countSetBits(x);
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Count how many 1s are in the binary form of 29 (11101).

The binary representation of 29 is 11101, which has 4 set bits (1s). Brian Kernighan's algorithm counts these by repeatedly turning off the rightmost set bit until the number becomes zero.

🧠 Conceptual

intermediate

Understanding Brian Kernighan's Algorithm Step

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

A It clears the rightmost set bit (1) in n.

B It sets the rightmost unset bit (0) in n to 1.

C It flips all bits of n.

D It shifts n to the left by one bit.

💡 Hint

Think about what happens when you subtract 1 from a number in binary.

Subtracting 1 from n flips the rightmost set bit and all bits after it. The AND operation with n clears that rightmost set bit, effectively removing one '1' from the binary representation.

🔧 Debug

advanced

Identify the Bug in Set Bits Counting Code

What error will the following code produce when counting set bits using Brian Kernighan's algorithm?

DSA C++

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

A Returns zero always.

B Returns correct count of set bits.

C Compilation error due to invalid operator usage.

D Infinite loop because n never becomes zero.

💡 Hint

Check what happens when you do n & (n + 1) repeatedly.

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

🚀 Application

advanced

Using Brian Kernighan's Algorithm to Count Set Bits in an Array

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

A

int totalSetBits = 0;
for (int num : arr) {
    while (num) {
        totalSetBits++;
        num >>= 1;
    }
}

B

int totalSetBits = 0;
for (int num : arr) {
    while (num) {
        num &= (num + 1);
        totalSetBits++;
    }
}

C

int totalSetBits = 0;
for (int num : arr) {
    while (num) {
        num &= (num - 1);
        totalSetBits++;
    }
}

D

int totalSetBits = 0;
for (int num : arr) {
    totalSetBits += __builtin_popcount(num);
}

💡 Hint

Brian Kernighan's algorithm clears the rightmost set bit in each iteration.

Option C correctly applies Brian Kernighan's algorithm to each number in the array, counting set bits by clearing the rightmost set bit until the number becomes zero.

Option C uses n & (n + 1), which is incorrect. Option C uses a built-in function, not the algorithm. Option C counts all bits, not just set bits.

🧠 Conceptual

expert

Why Brian Kernighan's Algorithm is Efficient

Why is Brian Kernighan's algorithm more efficient than checking each bit individually to count set bits?

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

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

C It uses recursion to reduce time complexity.

D It uses bit shifting which is faster than AND operations.

💡 Hint

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

Brian Kernighan's algorithm loops only once per set bit, skipping zero bits entirely, making it faster especially for numbers with few set bits.

Practice

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

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

C. It shifts the bits to the right one by one and counts all bits.

D. It converts the number to a string and counts '1' characters.

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 A

4. Quick Check:

   Clearing bits one by one counts set bits [OK]

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

Common Mistakes:

• Counting all bits instead of only set bits
• Using string conversion unnecessarily
• Shifting bits without checking if set

2. Which of the following is the correct syntax for the main loop in Brian Kernighan's algorithm in C++?

easy

A. while (n > 0) { count += n % 2; n /= 2; }

B. for (int i = 0; i < n; i++) { count += n & 1; n >>= 1; }

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

D. for (int i = 0; i < 32; i++) { count += (n >> i) & 1; }

Solution

1. Step 1: Identify Brian Kernighan's loop

   The algorithm uses while (n != 0) and clears the least significant set bit by n = n & (n - 1).

2. Step 2: Confirm increment of count

   Each iteration increments count by one for each cleared set bit.

3. Final Answer:

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

4. Quick Check:

   Loop clears bits and counts [OK]

Hint: Use while with n = n & (n-1) to clear bits [OK]

Common Mistakes:

• Using for loop instead of while
• Counting bits by shifting instead of clearing
• Using modulo instead of bitwise operations

3. What is the output of the following C++ code snippet using Brian Kernighan's algorithm?

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

int main() {
  int x = 13;
  std::cout << countSetBits(x);
  return 0;
}

medium

A. 5

B. 3

C. 2

D. 4

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

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Number of 1s in 1101 = 3 [OK]

Hint: Count 1s in binary of number for quick answer [OK]

Common Mistakes:

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

4. Identify the error in this Brian Kernighan algorithm implementation:

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

medium

A. Missing return statement.

B. Not initializing count to zero.

C. Using while (n > 0) instead of while (n != 0).

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

Solution

1. Step 1: Check bit clearing operation

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

2. Step 2: Effect of wrong operation

   Using n + 1 does not clear bits properly and causes incorrect count or infinite loop.

3. Final Answer:

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

4. Quick Check:

   Correct bit clearing uses n & (n - 1) [OK]

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

Common Mistakes:

• Replacing n - 1 with n + 1
• Confusing loop condition syntax
• Forgetting to increment count

5. Given an array of integers, how can you use Brian Kernighan's algorithm to find the total number of set bits in all elements? Choose the best approach.

hard

A. Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts.

B. Convert all integers to strings and count '1's in each string, then sum.

C. Use a single Brian Kernighan's algorithm call on the sum of all integers.

D. Count set bits only in the first element and multiply by array size.

Solution

1. Step 1: Understand counting set bits per element

   Brian Kernighan's algorithm counts set bits in one integer at a time.

2. Step 2: Apply algorithm to each array element

   Iterate through the array, count set bits for each element, and sum these counts for total.

3. Final Answer:

   Iterate over each element, apply Brian Kernighan's algorithm to count set bits, and sum all counts. -> Option A

4. Quick Check:

   Sum of individual counts gives total set bits [OK]

Hint: Count bits per element, then sum for total [OK]

Common Mistakes:

• Counting bits of sum instead of each element
• Using string conversion unnecessarily
• Assuming uniform bit count per element