[Solved] The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks: def reverseBits(n: int) -> int:... | Bit Manipulation

Bit Manipulation - Reverse Bits

The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks:

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = (n >> 16) | (n << 16)  # Bug here: missing mask
    return n

What is the bug in this code?

ALine 4: The mask 0x00ff00ff is incorrect for byte swapping.

BLine 1: Incorrect mask 0x55555555 used for swapping bits.

CLine 3: Left shift by 4 bits should be right shift.

DLine 5: Missing mask after shifting left and right by 16 bits, causing overflow beyond 32 bits.

Step-by-Step Solution

Solution:

Step 1: Identify the last step
The last line shifts bits by 16 left and right but does not mask the result to 32 bits.
Step 2: Understand impact
Without masking, bits can overflow beyond 32 bits, causing incorrect reversal results.
Final Answer:
Option D -> Option D
Quick Check:
Masking with 0xffffffff fixes overflow [OK]

Quick Trick: Always mask after large shifts to keep 32-bit result [OK]

Common Mistakes:

MISTAKES

Forgetting to mask after left shifts
Misusing masks in earlier steps
Confusing left and right shifts

Trap Explanation:

PITFALL

The missing mask is subtle because most shifts are masked; overflow only appears at last step.

Interviewer Note:

CONTEXT

Tests attention to detail and understanding of bitwise masking to prevent overflow.

Master "Reverse Bits" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Bit Manipulation Quizzes

The following code attempts to reverse bits of a 32-bit unsigned integer using divide and conquer masks:

Step 1: Identify the last step

Step 2: Understand impact

Final Answer:

Quick Check:

Want More Practice?