Reverse Bits

Share

Reverse bits of a given 32-bit unsigned integer and return the result as an unsigned integer.

Example 1
Input: n = 43261596 (binary: 00000010100101000001111010011100)
Output: 964176192 (binary: 00111001011110000010100101000000)
Explanation: The input's binary bits reversed gives the output.
Example 2
Input: n = 4294967293 (binary: 11111111111111111111111111111101)
Output: 3221225471 (binary: 10111111111111111111111111111111)

Solution Approach

Iterate 32 times. In each iteration, extract the lowest bit of n and shift it into the correct position in the result. Shift n right by 1 after each step.

  • Initialize result to 0.
  • For each of the 32 bit positions: left-shift result by 1, then OR with the current lowest bit of n.
  • Right-shift n by 1 to move to the next bit.
  • After 32 iterations, result holds the reversed bits.
Java
public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1; // unsigned right shift
        }
        return result;
    }
}
Complexity Analysis:

Time complexity: O(1). Always 32 iterations regardless of input.
Space complexity: O(1). Constant extra space.