Count Set Bits Brian Kernighan Algorithm in DSA C - 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 C code that counts set bits using Brian Kernighan's algorithm?

DSA C

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

int main() {
    int num = 29;
    int result = countSetBits(num);
    printf("%d\n", result);
    return 0;
}

A 5

B 3

C 4

D 6

💡 Hint

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

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

❓ Predict Output

intermediate

Result of Counting Set Bits for Zero Input

What will be the output when the input number is zero in the Brian Kernighan's set bit counting function?

DSA C

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

int main() {
    int num = 0;
    int result = countSetBits(num);
    printf("%d\n", result);
    return 0;
}

A 0

B Undefined behavior

C 1

D Infinite loop

💡 Hint

Consider how many set bits zero has.

Zero has no set bits, so the loop never runs and the count remains zero.

🔧 Debug

advanced

Identify the Error in Brian Kernighan's Algorithm Implementation

What error will the following code produce when compiled and run?

DSA C

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

int main() {
    int num = 15;
    int result = countSetBits(num);
    printf("%d\n", result);
    return 0;
}

A Compilation error due to operator precedence

B Runs correctly and outputs 4

C Runtime error due to invalid memory access

D Infinite loop

💡 Hint

Operator precedence: subtraction (-) has higher precedence than bitwise AND (&).

The expression `n & n - 1` is parsed as `n & (n - 1)` because subtraction has higher precedence than bitwise AND. The code runs correctly, clearing one set bit per iteration. 15 in binary is 1111, which has 4 set bits, so it outputs 4.

❓ Predict Output

advanced

Output of Counting Set Bits for a Large Number

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

DSA C

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

int main() {
    int num = 1023;
    int result = countSetBits(num);
    printf("%d\n", result);
    return 0;
}

A 11

B 9

C 8

D 10

💡 Hint

1023 in binary is all ones in the first 10 bits.

1023 is 2^10 - 1, which means its binary representation has 10 set bits.

🧠 Conceptual

expert

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

Which statement best explains why Brian Kernighan's algorithm is more efficient than checking each bit individually?

A It reduces the number of iterations to the number of set bits instead of total bits.

B It uses recursion to count bits faster than loops.

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

D It uses a lookup table for each byte to count bits.

💡 Hint

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

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 repeatedly clears the least significant set bit until the number becomes zero.

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

C. It shifts the number right and counts zeros.

D. It converts the number to decimal and counts digits.

Solution

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

   The algorithm uses n = n & (n-1) to clear the least significant set bit in each iteration.

2. Step 2: Effect of clearing bits

   Each operation 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 = It repeatedly clears the least significant set bit until the number becomes zero. [OK]

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

Common Mistakes:

• Counting zeros instead of ones
• Shifting without clearing bits
• Confusing decimal digits with bits

2. Which of the following is the correct syntax to clear the least significant set bit in C 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: Recall the bit clearing operation

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

2. Step 2: Verify other options

   Options A, B, and D do not clear the least significant set bit correctly.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using +1 instead of -1
• Using OR or XOR instead of AND
• Confusing bitwise operators

3. What is the output of the following C code snippet?

unsigned int n = 13; // binary 1101
int count = 0;
while (n) {
  n = n & (n - 1);
  count++;
}
printf("%d", count);

medium

A. 5

B. 2

C. 4

D. 3

Solution

1. Step 1: Analyze initial value and binary form

   13 in binary is 1101, which has three set bits (1s).

2. Step 2: Count iterations clearing bits

   Each loop clears one set bit: 1101 -> 1100 -> 1000 -> 0000, so loop runs 3 times.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Number of set bits in 13 = 3 [OK]

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

Common Mistakes:

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

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

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

medium

A. Missing initialization of count variable.

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

C. Incorrect return type of the function.

D. Loop condition should be while (n > 0).

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 for clearing bits

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

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using +1 instead of -1
• Ignoring loop condition correctness
• Forgetting to initialize count

5. Given an array of unsigned integers, which approach using Brian Kernighan's algorithm is most efficient to find the total count of set bits in all elements?

hard

A. Shift each number bit by bit and count set bits using bitwise AND with 1.

B. Convert each number to binary string and count '1's using string functions.

C. For each element, repeatedly clear least significant set bit and count until zero, then sum counts.

D. Use a lookup table for each byte and sum counts for all bytes in each number.

Solution

1. Step 1: Identify Brian Kernighan's approach

   For each element, repeatedly clear least significant set bit and count until zero, then sum counts.: For each element, repeatedly clear the least significant set bit until zero and count (using n = n & (n-1)), then sum the counts across elements. This is the direct application of Brian Kernighan's algorithm.

2. Step 2: Why it is most efficient using Brian Kernighan

   B (strings) is slow; C (shifts) is O(word size) always; D (lookup) is fast but a separate method, not Brian Kernighan's. Brian Kernighan excels for sparse bits (O(set bits) time).

3. Final Answer:

   For each element, repeatedly clear least significant set bit and count until zero, then sum counts. -> Option C

4. Quick Check:

   Brian Kernighan on array: apply n & (n-1) loop per element [OK]

Hint: Brian Kernighan per element: clear LSB until zero, sum counts [OK]

Common Mistakes:

• Using string conversion which is slow
• Bit shifting each bit without optimization
• Confusing lookup table with Brian Kernighan method