# Reverse Bits
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-bits)
Canonical: https://scaleengineer.com/dsa/problems/reverse-bits
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Divide and Conquer](https://scaleengineer.com/algorithms/divide-and-conquer)
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Nvidia](https://scaleengineer.com/companies/nvidia), [Qualcomm](https://scaleengineer.com/companies/qualcomm)
---
## 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](https://en.wikipedia.org/wiki/Two%27s%5Fcomplement). 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 = 11111111111111111111111111111101
**Output:**   3221225471 (10111111111111111111111111111111)
**Explanation:** The input binary string **11111111111111111111111111111101** represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is **10111111111111111111111111111111**.

**Constraints:**

* The input must be a **binary string** of length `32`

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

# Approaches
## String Conversion and Reversal
This approach is conceptually straightforward. It involves converting the 32-bit integer into its binary string representation, reversing this string, and then parsing the reversed string back into an integer.
**Time:** O(1) · **Space:** O(1)
**Pros:** Easy to understand and implement for those more familiar with string manipulation than bitwise operations.; Leverages high-level, built-in library functions.
**Cons:** Significantly less performant than bitwise approaches due to the overhead of string object creation, manipulation, and parsing.; Requires careful handling of padding and type conversion to correctly simulate unsigned 32-bit integer behavior in Java.
### Explanation
The core idea is to leverage built-in string manipulation functions. First, we need to get the 32-bit binary representation of the input integer `n`. Standard library functions like `Integer.toBinaryString(n)` do not produce a 32-bit string with leading zeros, so manual padding is required. Once we have the 32-bit string, we can use a `StringBuilder` to reverse it efficiently. Finally, the reversed binary string needs to be converted back to an integer. Since the reversed string can represent a number larger than `Integer.MAX_VALUE` (e.g., if the original LSB was 1, the new MSB will be 1, making it a large positive or negative number in signed context), it's safer to parse it as a `long` and then cast it to an `int`. This correctly handles the unsigned nature of the problem within Java's signed integer context.

```java
public class Solution {
    // you need to treat n as an unsigned value
    public int reverseBits(int n) {
        String binaryString = Integer.toBinaryString(n);
        
        // Pad with leading zeros to make it 32 bits long
        while (binaryString.length() < 32) {
            binaryString = "0" + binaryString;
        }
        
        StringBuilder reversedBuilder = new StringBuilder(binaryString);
        reversedBuilder.reverse();
        
        // Use Long.parseLong to handle unsigned values that would overflow a signed int
        // when the most significant bit is 1.
        long resultAsLong = Long.parseLong(reversedBuilder.toString(), 2);
        return (int) resultAsLong;
    }
}
```
### Algorithm
*   Convert the integer `n` to its binary string representation using `Integer.toBinaryString(n)`.
*   Pad the resulting string with leading zeros to ensure it has a length of 32.
*   Create a `StringBuilder` with this 32-bit string.
*   Reverse the `StringBuilder`.
*   Convert the reversed `StringBuilder` back to a string.
*   Parse the reversed binary string. Since the value might exceed `Integer.MAX_VALUE`, parse it as a `long` using `Long.parseLong(string, 2)` and then cast the result to an `int`.

## Bit by Bit Reversal
This is a classic and efficient approach that manipulates the bits directly using bitwise operators. It iterates through the 32 bits of the input integer, building the reversed integer one bit at a time.
**Time:** O(1) · **Space:** O(1)
**Pros:** Highly efficient as it uses low-level bitwise operations which are executed very quickly by the CPU.; Uses constant space, requiring only a few variables.; It is a fundamental technique in bit manipulation and widely applicable.
**Cons:** May be slightly less intuitive than the string approach for developers not comfortable with bitwise operations.
### Explanation
We initialize a result variable, say `result`, to 0. We will build the final reversed number in this variable. We loop 32 times, once for each bit of the integer. In each iteration, we first make space in our `result` number for the next bit by left-shifting it. Then, we extract the least significant bit (LSB) from the input number `n` and add it to our `result`. Finally, we discard the LSB from `n` by right-shifting it. It is crucial to use the unsigned right shift (`>>>`) to ensure that when a '1' is shifted from the most significant bit position (in the case of negative numbers), a '0' is shifted in, which correctly models the behavior of an unsigned integer. After 32 iterations, `n` will be 0, and `result` will hold all the bits of the original `n` in reverse order.

```java
public class Solution {
    // you need to treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            // Make space for the next bit
            result <<= 1;
            
            // Get the LSB of n and add it to result
            result |= (n & 1);
            
            // Discard the LSB of n. Use unsigned right shift.
            n >>>= 1;
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an integer variable `result` to 0.
*   Loop 32 times, for each bit in the integer.
*   In each iteration:
    1.  Left shift `result` by 1 (`result <<= 1;`) to make space for the next bit.
    2.  Extract the least significant bit (LSB) of `n` using a bitwise AND with 1 (`n & 1`).
    3.  Add this LSB to `result` using a bitwise OR (`result |= ...`).
    4.  Right shift `n` by 1 using the unsigned right shift operator (`n >>>= 1;`) to discard the LSB and process the next bit.
*   After 32 iterations, return `result`.

## Byte-wise Reversal with Caching
This approach, which directly addresses the follow-up question, optimizes for scenarios where the `reverseBits` function is called many times. It works by pre-calculating the reversed form of every possible 8-bit number (a byte) and storing these results in a lookup table. The 32-bit integer is then reversed by reversing its four constituent bytes using the table and stitching them back together.
**Time:** O(1) · **Space:** O(1)
**Pros:** Extremely fast for repeated calls, as it replaces a loop with a few table lookups and bitwise operations.; The ultimate optimization for this problem when performance under high-frequency calls is critical.
**Cons:** Requires extra space for the cache (e.g., 256 integers, which is 1 KB).; Incurs a one-time cost to pre-compute the cache, which might not be beneficial if the function is called only a few times.
### Explanation
The key insight is that reversing a 32-bit number is equivalent to reversing its four 8-bit bytes and then reversing the order of those bytes. For example, if `n = B3 B2 B1 B0` (where B_i are bytes from most to least significant), then `reverse(n) = reverse(B0) reverse(B1) reverse(B2) reverse(B3)`. We can pre-calculate `reverse(byte)` for all 256 possible byte values and store them. This cache is typically created once using a static initializer block. Then, for each call to `reverseBits`, we simply perform four byte extractions, four table lookups, three shifts, and three OR operations, which is significantly faster than iterating 32 times.

```java
public class Solution {
    // A static cache to store the reversed value of each of the 256 possible bytes.
    private static final int[] cache = new int[256];

    // The static initializer block runs once when the class is loaded, 
    // pre-populating the cache.
    static {
        for (int i = 0; i < 256; i++) {
            int b = i;
            int reversed = 0;
            for (int j = 0; j < 8; j++) {
                reversed <<= 1;
                reversed |= (b & 1);
                b >>= 1;
            }
            cache[i] = reversed;
        }
    }

    public int reverseBits(int n) {
        // Deconstruct n into 4 bytes, look up their reversed values in the cache,
        // and reconstruct the final integer.
        // Note the use of >>> (unsigned right shift) for correctness.
        return (cache[n & 0xFF] << 24) |
               (cache[(n >>> 8) & 0xFF] << 16) |
               (cache[(n >>> 16) & 0xFF] << 8) |
               (cache[(n >>> 24) & 0xFF]);
    }
}
```
### Algorithm
*   **Preprocessing (One-time cost):**
    1.  Create a cache, an integer array of size 256 (`cache[256]`).
    2.  Iterate from `i = 0` to 255. For each `i`, compute its 8-bit reversal and store it in `cache[i]`.
*   **`reverseBits` Function (Per-call):**
    1.  Break the 32-bit input `n` into four 8-bit bytes.
    2.  Look up the pre-computed reversed value of each byte from the `cache`.
    3.  Assemble the final result by shifting these reversed bytes to their new positions and combining them with bitwise OR.
        *   `result = (reversed_byte0 << 24) | (reversed_byte1 << 16) | (reversed_byte2 << 8) | reversed_byte3`

# Solutions
### Java

```java
public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n ) { int res = 0 ; for ( int i = 0 ; i < 32 && n != 0 ; ++ i ) { res |= (( n & 1 ) << ( 31 - i )); n >>>= 1 ; } return res ; } }
```

### JavaScript

```javascript
/** * @param {number} n - a positive integer * @return {number} - a positive integer */ var reverseBits = function ( n ) { let res = 0 ; for ( let i = 0 ; i < 32 && n > 0 ; ++ i ) { res |= ( n & 1 ) << ( 31 - i ); n >>>= 1 ; } return res >>> 0 ; };
```

### CPP

```cpp
class Solution {
public:
  uint32_t reverseBits(uint32_t n) {
    uint32_t res = 0;
    for (int i = 0; i < 32; ++i) {
      res |= ((n & 1) << (31 - i));
      n >>= 1;
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def reverseBits(self, n: int) -> int: res = 0 for i in range(32): res |= (n & 1) << (31 - i) n >>= 1 return res

```