Reverse Bits

---

Reverse Bits: Reverse bits of a given 32 bits unsigned integer.

• 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.

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 = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100
represents the unsigned integer 43261596, so return 964176192
which its binary representation is 00111001011110000010100101000000.

---

Constraints:

• The input must be a binary string of length 32.

---

Try this Problem on your own or check similar problems:

1. A Number After a Double Reversal
2. Number of 1 Bits
3. Reverse Integer

Solution:

Java

// you need treat n as an unsigned value
public int reverseBits(int n) {
    int result = 0, mask = 31;
    while(n != 0){
        result |= (n & 1) << mask;
        n >>>= 1;
        --mask;
    }
    return result;
}

JavaScript

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function (n) {
  let result = 0;
  let count = 32;

  while (count--) {
    result *= 2;
    result += n & 1;
    n = n >> 1;
  }
  return result;
};

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        mask = 31
        while n != 0:
            result |= (n & 1) << mask
            n >>= 1
            mask -= 1
        return result

C++

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        int mask = 31;
        while (n != 0) {
            result |= (n & 1) << mask;
            n >>= 1;
            --mask;
        }
        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(1)
• Space Complexity: O(1)

---

Explanation:

The space and time complexity are constant since we know we're operating only on binary strings (numbers) with 32 as their maximum length. We use most of the ideas on how to get the last bit and shift the current number to the right (until it reaches 0) from Number of 1 Bits. The only new thing is actually how to set the bits of reversed number, we know that in reversed representation the LSB (lowest significant bit) from the input will be placed as MSB (most significant bit) of the reversed number, so we create mask that will push the bits to the left with the << operator. Every new iteration we decrement our mask to target the next position in reversed representation. We do | (OR) concatenation with the result to set the bit (if the bit is 1, the | will result in 1 and for 0 we will have 0 as result, so the right bit will be set).