11.5 Reverse Bits

11.5.1 Problem Metadata

11.5.2 Description

Reverse bits of a given 32-bit unsigned integer.

Note: In some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. This should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

11.5.3 Examples

Input: n = 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Input: n = 4294967293 (11111111111111111111111111111101)
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

11.5.4 Constraints

  • The input must be a binary string of length 32

11.5.5 Follow-up

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

11.5.6 Solution 1 - String Reversal

11.5.6.1 Walkthrough

Convert the integer to its binary string representation, pad it to 32 bits with leading zeros, reverse the string character by character, and parse it back to an integer. This approach is straightforward but less efficient due to string operations.

The key steps are: 1. Convert to binary string (Java’s Integer.toBinaryString() omits leading zeros) 2. Pad with leading zeros to ensure 32-bit length 3. Reverse the string by prepending each character 4. Parse the reversed binary string back to an integer

Example: n = 43261596

Binary: "10100101000001111010011100" (26 bits)
After padding: "00000010100101000001111010011100" (32 bits)
After reversal: "00111001011110000010100101000000"
Result: 964176192

11.5.6.2 Analysis

  • Time Complexity: O(1) - always processes exactly 32 characters
  • Space Complexity: O(1) - stores a 32-character string

11.5.6.3 Implementation Steps

  1. Convert the integer n to binary string using Integer.toBinaryString(n).
  2. Calculate padding length needed: 32 - original string length.
  3. Prepend zeros to make the string exactly 32 bits long.
  4. Reverse the string by iterating through each character and prepending to a new string.
  5. Parse the reversed binary string to integer using Integer.parseInt(reversed, 2).
  6. Return the result.

11.5.6.4 Code - Java

public int reverseBits(int n) {
    int result = 0;

    String orig = Integer.toBinaryString(n);
    int padLen = 32 - orig.length();

    // Pad leading 0s
    for(int i = 0; i < padLen; i++) {
        orig = "0" + orig;
    }

    String reversed = "";

    for(char c : orig.toCharArray()) {
        reversed = c + reversed;
    }

    result = Integer.parseInt(reversed, 2);

    return result;
}

11.5.7 Solution 2 - Bit-by-Bit Reversal (Optimal)

11.5.7.1 Walkthrough

Process each of the 32 bits from right to left in the input number, building the result by placing each bit in the reversed position. Use bitwise operations to extract bits from the input and insert them into the result.

The algorithm works as follows: - Extract the least significant bit (LSB) from n using n & 1 - Shift result left by 1 to make room for the new bit - Insert the extracted bit into result using OR operation - Shift n right by 1 to process the next bit - Repeat 32 times

Visual Example 1: n = 43261596

Input: 00000010100101000001111010011100 (43261596) Output: 00111001011110000010100101000000 (964176192)

Let’s trace key iterations to see how bits are reversed:

Initial state:
n      = 00000010100101000001111010011100 (43261596)
result = 00000000000000000000000000000000 (0)

Iteration 1: Extract rightmost bit (0)
  n & 1        = 0
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000000
  n >> 1       = 00000001010010100000111101001110
  → result = 0

Iteration 2: Extract bit (0)
  n & 1        = 0
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000000
  n >> 1       = 00000000101001010000011110100111
  → result = 00

Iteration 3: Extract bit (1)
  n & 1        = 1
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000001
  n >> 1       = 00000000010100101000001111010011
  → result = 001

Iteration 4: Extract bit (1)
  n & 1        = 1
  result << 1  = 00000000000000000000000000000010
  result | bit = 00000000000000000000000000000011
  n >> 1       = 00000000001010010100000111101001
  → result = 0011

Iteration 5: Extract bit (1)
  n & 1        = 1
  result << 1  = 00000000000000000000000000000110
  result | bit = 00000000000000000000000000000111
  n >> 1       = 00000000000101001010000011110100
  → result = 00111

... (iterations 6-30 continue building the reversed pattern) ...

Iteration 31: Extract bit (0)
  n & 1        = 0
  result << 1  = 01110010111100000101001010000000
  result | bit = 01110010111100000101001010000000
  n >> 1       = 00000000000000000000000000000000
  → result = 01110010111100000101001010000000

Iteration 32: Extract bit (0) - leftmost bit of original
  n & 1        = 0
  result << 1  = 11100101111000001010010100000000
  result | bit = 00111001011110000010100101000000
  n >> 1       = 00000000000000000000000000000000
  → result = 00111001011110000010100101000000

Final state:
n      = 00000000000000000000000000000000 (0)
result = 00111001011110000010100101000000 (964176192)

Visual Example 2: n = 2147483644

Input: 01111111111111111111111111111100 (2147483644) Output: 00111111111111111111111111111110 (1073741822)

This example shows a pattern with mostly 1s being reversed:

Initial state:
n      = 01111111111111111111111111111100 (2147483644)
result = 00000000000000000000000000000000 (0)

Iteration 1: Extract rightmost bit (0)
  n & 1        = 0
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000000
  n >> 1       = 00111111111111111111111111111110
  → result = 0

Iteration 2: Extract bit (0)
  n & 1        = 0
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000000
  n >> 1       = 00011111111111111111111111111111
  → result = 00

Iteration 3: Extract bit (1)
  n & 1        = 1
  result << 1  = 00000000000000000000000000000000
  result | bit = 00000000000000000000000000000001
  n >> 1       = 00001111111111111111111111111111
  → result = 001

Iterations 4-31: All extract bit (1)
  Each iteration shifts result left and ORs with 1
  → result builds up: 0011, 00111, 001111, ..., 0011111111111111111111111111111

Iteration 32: Extract bit (0) - leftmost bit of original
  n & 1        = 0
  result << 1  = 01111111111111111111111111111110
  result | bit = 00111111111111111111111111111110
  n >> 1       = 00000000000000000000000000000000
  → result = 00111111111111111111111111111110

Final state:
n      = 00000000000000000000000000000000 (0)
result = 00111111111111111111111111111110 (1073741822)

Pattern observation:
Original: 01111111111111111111111111111100
          └─┬─┘└──────────┬────────────┘└┬┘
            0    (30 ones)               00
Reversed: 00111111111111111111111111111110
          └┬┘└──────────┬────────────┘└─┬─┘
           00   (30 ones)                0

Key Insight: Each bit from the right side of n gets placed on the left side of result. The rightmost bit of n becomes the leftmost bit of result, the second-rightmost becomes the second-leftmost, and so on. The algorithm processes bits in reverse order naturally by extracting from the right and building from the left.

11.5.7.2 Analysis

  • Time Complexity: O(1) - always performs exactly 32 iterations
  • Space Complexity: O(1) - uses only constant extra variables

11.5.7.3 Implementation Steps

  1. Initialize result = 0 to store the reversed bits.
  2. Loop 32 times (once for each bit position):
    • Shift result left by 1 bit to make room for the next bit.
    • Extract the least significant bit from n using n & 1.
    • Insert the extracted bit into result using result | bit.
    • Shift n right by 1 bit to process the next bit.
  3. Return result.

11.5.7.4 Code - Java

public int reverseBits(int n) {
    int result = 0;

    for(int i = 0; i < 32; i++) {
        result = result << 1;

        int bit = n & 0b01;
        result = result | bit;

        // Shift the input number to the right to process the next bit
        n = n >> 1;
    }

    return result;
}