Bird
Raised Fist0

The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results.

medium🐞 Bug Identification Q14 of Q15
Bit Manipulation - Counting Bits (0 to N)
The following code attempts to count set bits for all numbers from 0 to n using Brian Kernighan's trick. Identify the line containing the subtle bug that causes incorrect results. 
def countBits(n):
    res = []
    for i in range(1, n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res
ALine 3: for i in range(1, n + 1):
BLine 2: res = []
CLine 5: while x:
DLine 7: res.append(count)
Step-by-Step Solution
Solution:

  1. Step 1: Check loop range correctness

    The loop starts from 1, missing 0, so the count for 0 is never computed or appended.

  2. Step 2: Consequence of missing 0

    Result array length is n instead of n+1, causing mismatch and incorrect output for input including 0.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Including 0 is required to match problem specification [OK]
Quick Trick: Loop must start at 0 to include zero count [OK]
Common Mistakes:
MISTAKES
  • Starting loop at 1 instead of 0
  • Appending before counting
  • Incorrect while condition
Trap Explanation:
PITFALL
  • Starting at 1 looks plausible but misses the zero case, a common off-by-one error.
Interviewer Note:
CONTEXT
  • Checks attention to boundary conditions and correctness in loop ranges.
Master "Counting Bits (0 to N)" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Bit Manipulation Quizzes
Bitwise AND of Numbers Range - Bitwise AND of Numbers Range - Quiz 5medium Power of Four - Power of Four - Quiz 3easy Power of Four - Power of Four - Quiz 14medium Single Number (XOR Self-Cancellation) - Single Number (XOR Self-Cancellation) - Quiz 12easy Single Number (XOR Self-Cancellation) - Single Number (XOR Self-Cancellation) - Quiz 7medium Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 2easy Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 7medium Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 8hard Sum of Two Integers Without + Operator - Sum of Two Integers Without + Operator - Quiz 3easy UTF-8 Validation - UTF-8 Validation - Quiz 13medium