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.