Reverse Bits
The key idea
Walk the input one bit at a time from its least-significant end. Each bit you pull off the bottom of
n becomes the next bit pushed onto the top of the answer, so after 32 steps the bit order is exactly mirrored.Problem
Reverse the bits of a given 32-bit unsigned integer n.
Note that in some languages, such as Java, there is no unsigned integer type. In that case, both the input and output will be given as a signed integer type. They should not affect your implementation, because the internal binary representation of the integer is the same, whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.
Follow up: If this function is called many times, how would you optimize it?
Constraints
- The input must be a binary string of length
32
Examples
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Complexity
Time: O(1) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization