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:

1
2
3

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:

1
2
3

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?

Reverse Integer

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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;
    }
}
1
2
3
4
5
6
7

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:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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;
    }
}
1
2
3
4
5
6
7

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)