#190
Reverse Bits
Easy Shifts
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Reverse the order of the 32 bits of an integer.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: mirror the 32-bit pattern.
Why this works: take the last bit of n and push it onto the right of the result, 32 times. Leading zeros become trailing zeros.
Example (4 bits for short): n = 0011
step1: result 1, n 001step2: result 11, n 00step3: result 110, n 0step4: result 1100
✦Hints open one at a time
Build the result one bit at a time: shift the result left, then add the lowest bit of n.
Use n >>>= 1 so the sign bit doesn't get copied.
↗Approach
Loop exactly 32 times. Each step moves the lowest bit of n into the lowest position of the result after shifting the result left.
</>Solution (Java)
class Solution {
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result = (result << 1) | (n & 1); // append n's last bit
n >>>= 1; // unsigned shift
}
return result;
}
}!Common mistake
Stopping when n becomes 0. Leading zeros still need to become trailing zeros, so always run all 32 steps.
Complexity
- Time: O(32) = O(1).
- Space: O(1).
