# LeetCode 190: Reverse Bits

## Problem Restatement

We are given a 32-bit integer `n`.

We need to reverse its 32 bits and return the integer represented by the reversed bit pattern. The official statement asks us to reverse the bits of a given 32-bit integer.

For example, the binary form of `43261596` is:

```text
00000010100101000001111010011100
```

After reversing all 32 bits, we get:

```text
00111001011110000010100101000000
```

That binary value is `964176192`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 32-bit integer `n` |
| Output | Integer represented by the reversed 32-bit pattern |
| Operation | Reverse all 32 bit positions |
| Important detail | Always process exactly 32 bits |

Example function shape:

```python
def reverseBits(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 43261596
```

Binary:

```text
00000010100101000001111010011100
```

Reversed binary:

```text
00111001011110000010100101000000
```

Output:

```python
964176192
```

Example 2:

```python
n = 2147483644
```

Binary:

```text
01111111111111111111111111111100
```

Reversed binary:

```text
00111111111111111111111111111110
```

Output:

```python
1073741822
```

## First Thought: Convert to Binary String

A simple way is:

1. Convert `n` to a binary string.
2. Pad it to length `32`.
3. Reverse the string.
4. Convert it back to an integer.

In Python, that could look like this:

```python
bits = bin(n)[2:].zfill(32)
reversed_bits = bits[::-1]
answer = int(reversed_bits, 2)
```

This works, but it avoids the main idea of the problem. The problem is meant to practice bit manipulation.

We should solve it directly with shifts and bitwise operations.

## Key Insight

To reverse bits, we can read bits from right to left in `n` and build the answer from left to right.

At each step:

1. Take the last bit of `n`.
2. Append that bit to the right side of `ans`.
3. Shift `n` right to expose the next bit.

The last bit of `n` is obtained by:

```python
n & 1
```

For example:

| n binary ending | `n & 1` |
|---|---:|
| `...0` | `0` |
| `...1` | `1` |

To make room in the answer, shift `ans` left by one:

```python
ans <<= 1
```

Then add the extracted bit:

```python
ans |= n & 1
```

Do this exactly `32` times.

## Algorithm

1. Initialize `ans = 0`.
2. Repeat `32` times:
   - Shift `ans` left by one bit.
   - Add the lowest bit of `n` into `ans`.
   - Shift `n` right by one bit.
3. Return `ans`.

## Correctness

At the first iteration, the least significant bit of `n` becomes the first bit added to `ans`.

Since `ans` is shifted left before each new bit is added, earlier bits move toward more significant positions.

After one iteration, `ans` contains the original bit `0`.

After two iterations, `ans` contains original bits `0` and `1`, in that order.

After all `32` iterations, `ans` contains all original bits from least significant to most significant.

That is exactly the reverse of the original 32-bit representation.

Because the loop always runs exactly `32` times, leading zeros in the original number are also handled correctly.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | The loop always runs 32 times |
| Space | `O(1)` | Only a few integer variables are used |

Although there is a loop, the number of iterations does not grow with input size.

## Implementation

```python
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0

        for _ in range(32):
            ans <<= 1
            ans |= n & 1
            n >>= 1

        return ans
```

## Code Explanation

We start with an empty result:

```python
ans = 0
```

For each of the 32 bit positions:

```python
for _ in range(32):
```

we first shift the answer left:

```python
ans <<= 1
```

This creates one empty bit position on the right.

Then we copy the current lowest bit of `n` into that position:

```python
ans |= n & 1
```

Finally, we shift `n` right:

```python
n >>= 1
```

This removes the bit we just processed and exposes the next bit.

After 32 iterations, every bit has been moved to its reversed position.

## Alternative Implementation: Place Each Bit Directly

Another version extracts each bit and places it into its final reversed position.

```python
class Solution:
    def reverseBits(self, n: int) -> int:
        ans = 0

        for i in range(32):
            bit = (n >> i) & 1
            ans |= bit << (31 - i)

        return ans
```

Here, the bit at position `i` moves to position `31 - i`.

This version mirrors the definition of bit reversal directly.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.reverseBits(43261596) == 964176192
    assert s.reverseBits(2147483644) == 1073741822
    assert s.reverseBits(0) == 0
    assert s.reverseBits(1) == 2147483648
    assert s.reverseBits(2) == 1073741824

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `43261596` | Main example |
| `2147483644` | Example with many `1` bits |
| `0` | All bits are zero |
| `1` | Lowest bit moves to highest bit |
| `2` | Bit position `1` moves to position `30` |