Problem
You are given a 32-bit unsigned integern. Reverse the bits of the given integer and return the resulting 32-bit unsigned integer.
For example, if the binary representation starts with the bits
00000010100101000001111010011100, reversing all 32 bits produces 00111001011110000010100101000000.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 00000010100101000001111010011100Output
00111001011110000010100101000000Solution
We can solve this problem using bit manipulation.We process all 32 bits of the number one by one. For each iteration, we extract the rightmost bit of
n using n & 1 and append it to the result.
To make room for the next bit, we shift the result to the left by one position. We then shift
n to the right by one position to process its next bit.
For example, if the current bit of
n is 1, we add it to the result:
result = result << 1
result = result | (n & 1)class Solution {
public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
// Shift result left to make room for the next bit.
result <<= 1;
// Add the rightmost bit of n.
result |= (n & 1);
// Move to the next bit.
n >>= 1;
}
return result;
}
}
result <<= 1; shifts all bits of result one position to the left and creates an empty position at the right for the next bit.
In
n & 1 & is the bitwise AND operator. It extracts the rightmost bit of n.
|= means bitwise OR and assign. It puts the extracted bit into the empty position of result.
The important point is that because we first do
result <<= 1;, the rightmost bit of result becomes 0, so the OR operation simply puts the extracted bit into that position.
>>= means right-shift and assign. It shifts all bits of n one position to the right. This effectively moves to the next bit that needs to be processed.
Complexity
The loop always processes exactly 32 bits, resulting inO(1) time complexity. Only a constant number of variables is used, resulting in O(1) space complexity.