Reverse Bits

Reverse bits of a given 32 bits signed integer.

Example 1:

Input: n = 43261596

Output: 964176192

Explanation:

Integer: 43261596 Binary: 00000010100101000001111010011100

Integer: 964176192 Binary: 00111001011110000010100101000000

Example 2:

Input: n = 2147483644

Output: 1073741822

Explanation:

Integer: 2147483644 Binary: 01111111111111111111111111111100

Integer: 1073741822 Binary: 00111111111111111111111111111110

Constraints:

• 0 <= n <= 231 - 2
• n is even.

Follow up: If this function is called many times, how would you optimize it?

Approach: Bit by Bit (Iterative)

Algorithm

1. Initialize result = 0
2. For each of the 32 bits, shift result left by one and OR in the least significant bit of n
3. Shift n right by one
4. After 32 iterations, result holds the reversed bits

Time & Space Complexity

• Time Complexity: O(1) - fixed 32 iterations
• Space Complexity: O(1) - constant extra space

Java Implementation

public class ReverseBits {

    /**
     * Reverse the bits of a 32-bit integer.
     * @param n Input integer
     * @return Integer with reversed bits
     */
    public static int reverseBits(int n) {
        int result = 0;

        for (int i = 0; i < 32; i++) {
            result <<= 1;
            result |= (n & 1);
            n >>= 1;
        }

        return result;
    }

    // Test method
    public static void main(String[] args) {
        int n1 = 43261596;
        System.out.println("Input: n = 43261596");
        System.out.println("Output: " + reverseBits(n1)); // Expected: 964176192

        int n2 = 2147483644;
        System.out.println("Input: n = 2147483644");
        System.out.println("Output: " + reverseBits(n2)); // Expected: 1073741822
    }
}

Example Walkthrough

For n = 43261596 (binary 00000010100101000001111010011100):

After reversing all 32 bits, the binary becomes 00111001011110000010100101000000, which is 964176192 in decimal.

Key Points

1. Fixed 32 Bits: All leading zeros are included in the reversal
2. Shift and Extract: result <<= 1 makes room; result |= (n & 1) inserts the LSB
3. Arithmetic vs Logical Shift: n >>= 1 works fine because the bits of interest are consumed before sign extension matters
4. Unsigned Result: Java returns int, but the reversed value is interpreted correctly by the problem’s test cases
5. Follow-up: For repeated calls, a 16-bit (or byte) lookup table can reverse 4 chunks and combine them