Reverse Bits

Problem

Reverse bits of a given 32 bits unsigned integer.

Note:

• Note that 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. They should not affect your implementation, as the integer's internal binary representation 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.

Examples

Example 1:

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

Example 2:

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

Follow up

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

Solution

Method 1 - Iterative reversal using left shift and in-place modification

To reverse the bits of a 32-bit unsigned integer:

1. Initialise the result as 0.
2. Iterate 32 times (once for each bit in the integer).
3. In each iteration, shift the result to the left by 1 bit to make room for the next bit.
4. Get the least significant bit (LSB) of the input and add it to the result.
5. Shift the input to the right by 1 bit to process the next bit.
6. Return the result after processing all 32 bits.

Code

Java

public class Solution {
    public int reverseBits(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            ans <<= 1;
            ans |= (n & 1);
            n >>= 1;
        }
        return ans;
    }
}

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        ans: int = 0
        for _ in range(32):
            ans = (ans << 1) | (n & 1)
            n >>= 1
        return ans

Complexity

• ⏰ Time complexity: O(1) because the number of operations is constant and does not depend on the input size.
• 🧺 Space complexity: O(1) as only a fixed amount of extra space is used.

Method 2 - Reversing Bits Using Positional Mapping

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/U6N0c_GjQJc" frameborder="0" allowfullscreen></iframe></div>

Code

Java

public class Solution {
    public int reverseBits(int n) {
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            int bit = (n >> i) & 1;
            ans |= (bit << (31 - i));
        }
        return ans;
    }
}

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0
        for i in range(32):
            bit = (n >> i) & 1  # Extract the bit at position i
            ans |= (bit << (31 - i))  # Place it at the reversed position
        return ans

Complexity

• ⏰ Time complexity: O(1)
• 🧺 Space complexity: O(1)

Method 3 - Divide-and-conquer bit masks

Intuition

Reverse the bits by swapping bit-blocks of increasing granularity: first swap every pair of bits, then swap 2-bit groups, then 4-bit groups, and so on. Using constant masks and shifts does a fixed number of operations (log2(word_size) steps) and runs in constant time for fixed-width integers.

Approach

• Treat x as a 32-bit word.
• Apply a sequence of mask-and-shift operations to swap bit-blocks:
  1. Swap adjacent bits using mask 0x55555555.
  2. Swap 2-bit groups using mask 0x33333333.
  3. Swap 4-bit groups using mask 0x0f0f0f0f.
  4. Swap 8-bit groups using mask 0x00ff00ff.
  5. Swap 16-bit halves.
• Return the resulting 32-bit integer.

Edge cases

• If x == 0 the result is 0.

Code

C++

class Solution {
 public:
  uint32_t reverseBits(uint32_t x) {
    x = ((x >> 1) & 0x55555555u) | ((x & 0x55555555u) << 1);
    x = ((x >> 2) & 0x33333333u) | ((x & 0x33333333u) << 2);
    x = ((x >> 4) & 0x0f0f0f0fu) | ((x & 0x0f0f0f0fu) << 4);
    x = ((x >> 8) & 0x00ff00ffu) | ((x & 0x00ff00ffu) << 8);
    x = (x >> 16) | (x << 16);
    return x;
  }
};

Go

package main

func reverseBits(x uint32) uint32 {
    x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1)
    x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2)
    x = ((x >> 4) & 0x0f0f0f0f) | ((x & 0x0f0f0f0f) << 4)
    x = ((x >> 8) & 0x00ff00ff) | ((x & 0x00ff00ff) << 8)
    x = (x >> 16) | (x << 16)
    return x
}

Java

class Solution {
  public int reverseBits(int x) {
    int y = x;
    y = ((y >>> 1) & 0x55555555) | ((y & 0x55555555) << 1);
    y = ((y >>> 2) & 0x33333333) | ((y & 0x33333333) << 2);
    y = ((y >>> 4) & 0x0f0f0f0f) | ((y & 0x0f0f0f0f) << 4);
    y = ((y >>> 8) & 0x00ff00ff) | ((y & 0x00ff00ff) << 8);
    y = (y >>> 16) | (y << 16);
    return y;
  }
}

Python

class Solution:
    def reverse_bits(self, x: int) -> int:
        x &= 0xFFFFFFFF
        x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1)
        x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2)
        x = ((x >> 4) & 0x0f0f0f0f) | ((x & 0x0f0f0f0f) << 4)
        x = ((x >> 8) & 0x00ff00ff) | ((x & 0x00ff00ff) << 8)
        x = ((x >> 16) & 0x0000ffff) | ((x & 0x0000ffff) << 16)
        return x & 0xFFFFFFFF

Complexity

• ⏰ Time complexity: O(1), the algorithm performs a fixed number of bitwise operations (5 mask-and-shift steps) on a fixed-size word.
• 🧺 Space complexity: O(1), only constant extra space used.