[Solved] Consider the following Python code that uses Brian Kernighan's bit counting trick to count set bits from 0 to n. What is the output when n = 3? def countBits(n):... What is the output when n = 3? | Bit Manipulation

Bit Manipulation - Counting Bits (0 to N)

Consider the following Python code that uses Brian Kernighan's bit counting trick to count set bits from 0 to n. What is the output when n = 3?

def countBits(n):
    res = []
    for i in range(n + 1):
        count = 0
        x = i
        while x:
            x &= x - 1
            count += 1
        res.append(count)
    return res

print(countBits(3))

A[1, 1, 1, 1]

B[0, 1, 2, 2]

C[0, 0, 1, 2]

D[0, 1, 1, 2]

Step-by-Step Solution

Solution:

Step 1: Trace countBits for i=0 to 3
i=0: binary 0, count=0; i=1: binary 1, count=1; i=2: binary 10, count=1; i=3: binary 11, count=2.
Step 2: Confirm final result list
Result list is [0, 1, 1, 2].
Final Answer:
Option D -> Option D
Quick Check:
Matches manual bit count for each number [OK]

Quick Trick: Count bits by clearing least significant set bit [OK]

Common Mistakes:

MISTAKES

Off-by-one in range
Miscounting bits for 2 or 3
Confusing count initialization

Trap Explanation:

PITFALL

Counting bits for 2 and 3 is often confused due to binary representation differences.

Interviewer Note:

CONTEXT

Checks ability to mentally execute bit manipulation code and track variables.

Master "Counting Bits (0 to N)" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Bit Manipulation Quizzes

Consider the following Python code that uses Brian Kernighan's bit counting trick to count set bits from 0 to n. What is the output when n = 3?

Step 1: Trace countBits for i=0 to 3

Step 2: Confirm final result list

Final Answer:

Quick Check:

Want More Practice?