Reverse Bits

LeetCode 190: Reverse Bits Solution & Explanation

Problem Overview

TL;DR: Extract the least significant bit 32 times with bitwise AND, append each extracted bit to a result by shifting left, then interpret the resulting 32-bit pattern as a signed integer.

In LeetCode 190: Reverse Bits, the input is treated as exactly 32 bits, including leading zeros. The task is to reverse the positions of those bits and return the reversed pattern as a signed 32-bit two's-complement integer. This LeetCode 190 Solution uses fixed-width bit manipulation rather than converting the number to a variable-length binary representation.

For example, the lowest bit of the input becomes the highest bit of the result, while the original highest bit becomes the lowest bit. Because the output is still a signed 32-bit value, a set bit at position 31 represents a negative number.

Brute Force Approach for Reverse Bits

A naive approach is to convert the integer into a binary representation, reverse the representation, and convert it back.

A basic version might work as follows:

bits = binary representation of n
pad bits with leading zeros until its length is 32
reverse bits
interpret the reversed 32-bit pattern as a signed integer
return the result

Pseudo-code:

bits = convert n to binary
while length(bits) < 32:
    prepend "0" to bits

reversedBits = reverse(bits)
result = convert reversedBits to an integer

if bit 31 of reversedBits is 1:
    result -= 2^32

return result

This approach has two important problems:

1. A normal binary conversion of a negative integer may include a minus sign rather than its 32-bit two's-complement pattern.
2. Omitting leading zeros changes the positions of all bits during reversal.

The time complexity is technically O(32) for this problem because the input width is fixed. Therefore, it does not genuinely cause a Time Limit Exceeded error under these constraints. Its failure is primarily a representation and correctness failure: treating the number as a variable-length binary value does not satisfy the required fixed-width 32-bit interpretation.

The bitwise approach avoids both issues by explicitly processing exactly 32 positions.

Algorithm Strategy: Bit Manipulation Patterns

1. Convert the signed input into its unsigned 32-bit pattern.
2. Initialize the reversed result to zero.
3. Repeat exactly 32 times:
   • Extract the current lowest bit using bitwise AND with 1.
   • Shift the result left by one position.
   • Insert the extracted bit into the result.
   • Shift the input right by one position.
4. Check whether bit 31 of the constructed result is set.
5. If it is set, subtract 2^32 to interpret the unsigned 32-bit pattern as a signed two's-complement integer.
6. Return the signed result.

The fixed loop count enforces the 32-bit boundary, including leading zeros.

Execution Flow

1. Normalize the input pattern

   • The input is masked or cast so its lower 32 bits represent the required two's-complement pattern.
   • This prevents signed-language behavior from changing the intended bit sequence.

2. Initialize state

   • reversed starts at zero.
   • No result bits have been processed yet.

3. Process the current least significant bit

   • bits & 1 returns either 0 or 1.
   • This is the next bit that must be placed into the reversed result.

4. Append the extracted bit

   • Shift reversed left by one.
   • Use bitwise OR to place the extracted bit in the new lowest position.

5. Advance the input

   • Shift bits right by one.
   • The next original bit becomes the least significant bit.

6. Repeat for all 32 positions

   • Even leading zeros are processed.
   • The final result contains all input bits in reverse order.

7. Interpret the result as signed

   • If result bit 31 is clear, the value is already nonnegative.
   • If result bit 31 is set, subtract 2^32 to obtain the signed two's-complement value.

For n = 5, the relevant input pattern begins with:

00000000000000000000000000000101

The extracted bits begin with 1, 0, and 1. After all 32 iterations, these become the highest corresponding positions in the reversed pattern.

Proof of Correctness

We prove that the algorithm returns the 32-bit pattern obtained by reversing the input bits.

Let the original input bit at position j be b_j, where 0 <= j < 32.

At iteration i:

1. Before extraction, the input has been shifted right exactly i times.
2. Therefore, its least significant bit is the original bit b_i.
3. The operation bits & 1 extracts exactly b_i.
4. Before inserting b_i, the result is shifted left once. Thus, after iteration i, the newly inserted bit occupies position 0, while all bits collected in earlier iterations move one position higher.
5. Consequently, after iteration i, the extracted sequence b_0, b_1, ..., b_i appears in the result as:
   textCopy

   b_i ... b_1 b_0

After 32 iterations, the result contains:

b31 b30 ... b1 b0

from highest to lowest position, which is exactly the reversal of the original 32-bit sequence:

b0 b1 ... b30 b31

The final signed conversion does not change the bit pattern. It only interprets a result with bit 31 set according to two's-complement rules. Therefore, the algorithm always returns the required signed 32-bit value.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 231: Power of Two
• LeetCode 191: Number of 1 Bits

For Power of Two, bitwise operations inspect whether the set-bit structure satisfies a required condition. For Number of 1 Bits, value & 1 or related bitwise reductions inspect and count set bits. LeetCode 190: Reverse Bits applies the same low-level bit inspection principle while reconstructing the bits in the opposite order, making it a popular interview question and an optimal solution for interviews involving fixed-width integer representations.

Reference Implementation

C++ Solution for LeetCode 190

1class Solution {
2public:
3    int reverseBits(int n) {
4        unsigned long long bits = static_cast<unsigned int>(n);
5        unsigned long long reversed = 0;
6
7        for (int i = 0; i < 32; ++i) {
8            reversed = (reversed << 1) | (bits & 1ULL);
9            bits >>= 1;
10        }
11
12        if (reversed >= (1ULL << 31)) {
13            return static_cast<int>(reversed - (1ULL << 32));
14        }
15        return static_cast<int>(reversed);
16    }
17};

The cast to unsigned int preserves the lower 32 bits of the signed input as an unsigned bit pattern. The wider unsigned long long variables allow the code to construct and inspect the complete 32-bit result safely.

Java Solution for LeetCode 190

1class Solution {
2    public int reverseBits(int n) {
3        long unsignedN = n & 0xFFFFFFFFL;
4        long reversedBits = 0;
5
6        for (int i = 0; i < 32; i++) {
7            reversedBits = (reversedBits << 1) | (unsignedN & 1);
8            unsignedN >>= 1;
9        }
10
11        if ((reversedBits & 0x80000000L) != 0) {
12            reversedBits -= 1L << 32;
13        }
14
15        return (int) reversedBits;
16    }
17}

The mask 0xFFFFFFFFL converts the signed Java int into a nonnegative long containing the same 32-bit pattern. This makes the right shift behave as a logical shift for the processed value.

Python Solution for LeetCode 190

1class Solution:
2    def reverseBits(self, n: int) -> int:
3        n &= 0xFFFFFFFF
4        reversed_bits = 0
5
6        for _ in range(32):
7            reversed_bits = (reversed_bits << 1) | (n & 1)
8            n >>= 1
9
10        if reversed_bits & 0x80000000:
11            reversed_bits -= 1 << 32
12
13        return reversed_bits

Python integers are not restricted to 32 bits, so n &= 0xFFFFFFFF is necessary to retain only the required input pattern. The final subtraction converts a result with bit 31 set into its signed 32-bit interpretation.