Practice Reverse Bits
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Reverse bits of a given 32 bits unsigned integer. Follow up: If this function is called many times, how would you optimize it?
Source: Reverse Bits on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
n = 43261596
964176192
# Example 2
n = 2147483644
1073741822
Constraints
How to solve Reverse Bits
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Peeling off the lowest bit of the input and pushing it onto the low end of a result that is shifted left each time reverses the bit order in exactly 32 steps, without ever converting to a string.
Why brute force is not enough
Formatting the integer as a 32-character binary string, reversing it, and parsing it back is also constant time but allocates on every call and often drops leading zeros, producing a wrong width. For the follow-up where the function is called many times, per-call string work dominates.
Approach
- Start with a result of zero and treat the input as an unsigned 32-bit value.
- Repeat exactly 32 times: shift the result left by one, then OR in the lowest bit of the input, then shift the input right by one using an unsigned shift.
- Do not stop early when the input becomes zero; the remaining shifts of the result are what place the collected bits in their final high positions.
- Return the result, masking to 32 bits in languages with arbitrary-precision integers.
- For many calls, cache the reversal of each of the 256 possible bytes and assemble four lookups, or use the masked swap technique: swap the two 16-bit halves, then 8-bit groups, then 4-bit, 2-bit, and single bits.
Walkthrough of Example 2
n = 2147483644 → 1073741822
- 2147483644 is 2^31 minus 4, whose 32-bit form is a leading 0, then 29 ones, then two zeros.
- The first two iterations pull out the two low zeros; the result is still 0.
- The next 29 iterations each pull out a 1, so the result becomes 29 consecutive ones.
- The final iteration pulls out the leading 0, shifting the result left once more: 29 ones followed by a 0, with two leading zeros in 32 bits.
- That pattern is 2^30 minus 2, which equals 1073741822.
Time and space
Time O(1) · Space O(1). The loop runs a fixed 32 iterations regardless of input value, and only two integers are held; with a byte table the lookup is still constant with 256 cached entries.
Interview pitfalls
- Using a signed right shift in Java or similar, which smears the sign bit for inputs with the top bit set.
- Breaking out of the loop once the input is zero, leaving the result unshifted and too small.
- In Python, forgetting that integers are unbounded, so the result must be masked to 32 bits and the input treated as unsigned.
- Building the result from a string and forgetting to left-pad to 32 characters.
- Off-by-one in the iteration count: 31 iterations silently drops one bit.
Follow-up questions interviewers ask
- How would you reverse the bits of a 64-bit value, and what changes in the masked swap approach?
- Design the byte-lookup cache: how large is it and how do you combine four results?
- Reverse only the lowest k bits while leaving the rest untouched.
Further reading on the technique: Bit manipulation
Related LeetCode Problems
Practice more problems similar to Reverse Bits.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.