Reverse bits of a given 32 bits signed integer.
Example 1:
Input: n = 43261596
Output: 964176192
Explanation:
| Integer | Binary |
| 43261596 | 00000010100101000001111010011100 |
| 964176192 | 00111001011110000010100101000000 |
Example 2:
Input: n = 2147483644
Output: 1073741822
Explanation:
| Integer | Binary |
| 2147483644 | 01111111111111111111111111111100 |
| 1073741822 | 00111111111111111111111111111110 |
Constraints:
- 0 <= n <= 231 - 2
- n is even
My Solution
To solve this problem we can just capture each bit by AND-ing by 1, reversing that bit in the output by OR-ing with 31-(bitcount) and then move on to the next bit by right shifting by 1. We also increment count to set the next reversed bit.
Time complexity would be O(1) because we have to deal with 32 bits, which is a constant. Space complexity would also be O(1), since we require constant extra space.
class Solution {
public int reverseBits(int n) {
int out = 0;
int count = 0;
while (n > 0) {
int bit = n & 1;
out |= (bit << (31-count));
n >>= 1;
count++;
}
return out;
}
}