Reverse Bits
Problem
Given a 32-bit unsigned integer n, return the integer obtained by reversing its bits.
- The input is a 32-bit unsigned integer.
- The output must also be a 32-bit unsigned integer.
Example
n = 43261596964176192The binary representation of 43261596 is 00000010100101000001111010011100. Reversing the bits yields 00111001011110000010100101000000, which corresponds to 964176192 in decimal. The algorithm iterates over each bit position i from 0 to 31, extracts the bit at position i, and sets it at position 31 - i in the result. This systematic reversal ensures the bits are flipped in order.
Approach
Straightforward Solution
A naive approach might convert the integer to a 32-character binary string, reverse the string, and convert back to an integer. This approach is inefficient due to string manipulation overhead and does not leverage bitwise operations.
Core Observation
Reversing bits is a positional transformation where the bit at index i in the input moves to index 31 - i in the output. This is a fixed mapping independent of the bit values themselves.
Path to Optimal
The key insight is to use bitwise operations to extract and reposition bits directly. By iterating over each bit position, the algorithm extracts the bit using a right shift and bitwise AND, then places it in the reversed position using a left shift and bitwise OR. This avoids string conversions and operates in constant time with respect to the fixed 32-bit size.
Optimal Approach
Iterate over all 32 bit positions. For each position i, extract the bit at i by shifting n right by i and masking with 1. Then shift this bit left by (31 - i) to place it in the reversed position and combine it into the result using bitwise OR. After processing all bits, return the accumulated result. This approach runs in O(1) time since the bit width is fixed and uses O(1) space.
Time
O(1)
The algorithm performs a fixed 32-iteration loop regardless of input size, so the time complexity is constant.
Space
O(1)
Only a fixed number of integer variables are used, with no additional data structures proportional to input size.
Pattern Spotlight
Bit Manipulation (Bitwise Position Reversal)
When reversing bits, treat the problem as a fixed positional mapping where each bit's index i maps to 31 - i; extract and reposition bits using shifts and masks without converting to strings.
Solution
| 1 | class Solution:
|
| 2 | def reverseBits(self, n: int) -> int:
|
| 3 | res = 0
|
| 4 | for i in range(32):
|
| 5 | bit = (n >> i) & 1
|
| 6 | res = res | (bit << (31 - i))
|
| 7 | return res |
Step-by-Step Solution
Initialize Result Accumulator
| 3 | res = 0
|
Objective
To prepare a variable to accumulate the reversed bits as they are computed.
Key Insight
Starting with zero ensures that the result has no bits set initially. As bits are extracted and repositioned, they are combined into this accumulator using bitwise OR, building the reversed bit pattern incrementally.
Interview Quick-Check
Core Logic
Initialize the result to zero to serve as a clean slate for accumulating reversed bits.
Common Pitfalls & Bugs
Failing to initialize the result to zero can lead to incorrect results due to residual bits.
Extract and Reposition Each Bit in a Fixed Loop
| 4 | for i in range(32):
|
| 5 | bit = (n >> i) & 1
|
| 6 | res = res | (bit << (31 - i))
|
Objective
To iterate over each bit position, extract the bit, and place it in the reversed position within the result.
Key Insight
By shifting the input right by i and masking with 1, the algorithm isolates the bit at position i. Shifting this bit left by (31 - i) repositions it to its reversed index. Using bitwise OR merges this bit into the result without disturbing previously set bits. This process repeated for all 32 bits constructs the fully reversed bit pattern.
Interview Quick-Check
Core Logic
Extract each bit using right shift and mask, then reposition it using left shift before combining with the result using bitwise OR.
State & Boundaries
Loop runs exactly 32 times, covering all bits in a 32-bit integer.
Common Pitfalls & Bugs
Incorrect shift amounts or masking can cause bits to be misplaced or lost.
Return the Fully Reversed Bit Integer
| 7 | return res |
Objective
To output the integer representing the reversed bit pattern after processing all bits.
Key Insight
After all bits have been repositioned and combined, the result holds the reversed bit sequence. Returning this value completes the transformation from the original integer to its bitwise reverse.
Interview Quick-Check
Core Logic
Return the accumulated result which now contains the reversed bits.
Line Analysis
This solution has 1 Critical line interviewers watch for.
res = res | (bit << (31 - i))Shift the extracted bit to its reversed position and combine it into the result using bitwise OR.
Shifting the bit left by (31 - i) repositions it to the reversed index, and bitwise OR merges it into the result without altering previously set bits, cumulatively building the reversed bit pattern.
bit = (n >> i) & 1Extract the bit at position i by right-shifting and masking with 1.
Right-shifting by i moves the target bit to the least significant position, and masking with 1 isolates it, enabling precise extraction of each bit.
res = 0Initialize the result variable to zero to accumulate reversed bits.
Starting with zero ensures no bits are set initially, providing a clean accumulator for the reversed bits to be combined into.
return resReturn the integer representing the reversed bits.
After processing all bits, the result holds the reversed bit sequence, so returning it completes the transformation.
for i in range(32):Iterate over all 32 bit positions of the input integer.
The fixed loop ensures every bit in the 32-bit integer is processed exactly once, covering the entire input.
Test Your Understanding
Why is it necessary to shift the extracted bit to position (31 - i) before OR-ing it into the result?
Because reversing bits means the bit originally at position i must be placed at position 31 - i in the output; shifting aligns the bit to its reversed position before combining it into the result.
Related Problems
Bit Manipulation pattern
Don't just read it. Drill it.
Reconstruct Reverse Bits from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reverse Bits drill