190. Reverse Bits - Solution & Explanation

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

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?

Approach overview

Problem Overview: You are given a 32-bit unsigned integer and must reverse its binary representation. The least significant bit becomes the most significant bit, the second least becomes the second most, and so on. The result is another 32-bit integer formed from this reversed bit order.

Approach 1: Bitwise Shift and OR (Time: O(32), Space: O(1))

This method builds the reversed number one bit at a time. Iterate through all 32 bits of the input integer. At each step, extract the last bit using n & 1, shift the result left by one position, and append the extracted bit using a bitwise OR. Then shift the original number right using n >> 1. After 32 iterations, the constructed number contains the reversed bit order. This approach relies purely on basic bit manipulation operations and is easy to implement in any language.

The key idea is treating the integer as a stream of bits. Each iteration pulls the least significant bit and pushes it into the reversed result from the left side. Because a 32-bit integer always has a fixed width, the loop runs exactly 32 times, making the algorithm effectively constant time. This is the most common solution used in interviews and coding platforms.

Approach 2: Bit Manipulation with Precomputed Masks (Time: O(1), Space: O(1))

This approach reverses bits in groups instead of processing them one by one. It uses precomputed bit masks to swap halves, then quarters, then smaller groups of bits. For example, swap the left and right 16-bit halves, then swap 8-bit groups, then 4-bit groups, and continue until single bits are swapped. Each stage uses masks and shifts such as (n & mask) << k and (n >> k) & mask to reposition groups of bits.

The idea follows a divide and conquer pattern. Instead of reversing sequentially, the algorithm repeatedly splits the integer into smaller segments and swaps them using bit masks. Because the number of operations is fixed and independent of input value, the complexity is constant time. This technique appears frequently in systems programming and performance-critical bit operations.

Recommended for interviews: The shift-and-OR approach is what most interviewers expect. It demonstrates clear understanding of bit manipulation fundamentals such as masking, shifting, and constructing integers bit by bit. The mask-based divide-and-conquer technique is more advanced and useful when discussing optimized bit tricks or low-level performance.

Approach 1: Approach 1: Bitwise Shift and OR

In this approach, we utilize bitwise operations to reverse the bits. We iterate through each bit of the number from the least significant bit (LSB) to the most significant bit (MSB), shifting the resultant bits to the left and using the bitwise OR operation to set the bits in the reversed order.

Python

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

Java

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        return result;
    }
}

C++

#include <cstdint>

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

JavaScript

var reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result >>> 0; // Unsigned right shift to handle JavaScript's bitwise operations
};

#include <stdint.h>

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>= 1;
    }
    return result;
}

public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

Python’s implementation also uses bitwise operations. Python integers can handle arbitrary precision, but for this problem, only the first 32 bits are considered.

Complexity

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

Try this approach in the editor

Approach 2: Approach 2: Bit Manipulation with Precomputed Masks

This approach could be optimized by precomputing masks that handle groups of bits. This reduces the need for iterating through each bit and instead processes larger chunks of bits through bit manipulation techniques.

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
        n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
        n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4)
        n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8)
        n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16)
        return n

Java

public class Solution {
    public int reverseBits(int n) {
        n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
        n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
        n = ((n >>> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4);
        n = ((n >>> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8);
        n = ((n >>> 16) & 0x0000ffff) | ((n & 0x0000ffff) << 16);
        return n;
    }
}

C++

#include <cstdint>

uint32_t reverseBits(uint32_t n) {
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
    n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
    n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
    n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
    return n;
}

JavaScript

var reverseBits = function(n) {
    n = ((n >>> 1) & 0x55555555) | ((n & 0x55555555) << 1);
    n = ((n >>> 2) & 0x33333333) | ((n & 0x33333333) << 2);
    n = ((n >>> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
    n = ((n >>> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
    n = ((n >>> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
    return n >>> 0;
};

#include <stdint.h>

uint32_t reverseBits(uint32_t n) {
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
    n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
    n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
    n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
    return n;
}

public class Solution {
    public uint reverseBits(uint n) {
        n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1);
        n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2);
        n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4);
        n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8);
        n = ((n >> 16) & 0x0000FFFF) | ((n & 0x0000FFFF) << 16);
        return n;
    }
}

Python's implementation uses integer representation for masks to perform reversal. Even though Python supports arbitrary-precision integers, the fixed operation sizes ensure we focus only on the 32 necessary bits.

Complexity

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

Try this approach in the editor

Approach 3: Bit Manipulation

We can extract each bit of n from the lowest bit to the highest bit, and then place it at the corresponding position of ans.

For example, for the i-th bit, we can extract the i-th bit of n and place it at the (31 - i)-th bit of ans by (n \& 1) \ll (31 - i), and then right shift n by one bit.

The time complexity is O(log n), and the space complexity is O(1).

TypeScript

function reverseBits(n: number): number {
    let ans = 0;
    for (let i = 0; i < 32 && n; ++i) {
        ans |= (n & 1) << (31 - i);
        n >>= 1;
    }
    return ans >>> 0;
}

func reverseBits(n uint32) (ans uint32) {
	for i := 0; i < 32; i++ {
		ans |= (n & 1) << (31 - i)
		n >>= 1
	}
	return
}

Rust

impl Solution {
    pub fn reverse_bits(mut n: u32) -> u32 {
        let mut ans = 0;
        for i in 0..32 {
            ans |= (n & 1) << (31 - i);
            n >>= 1;
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Bitwise Shift and OR	Time Complexity: O(1). Space Complexity: O(1).
Approach 2: Bit Manipulation with Precomputed Masks	Time Complexity: O(1). Space Complexity: O(1).
Bit Manipulation	–

Complexity analysis

Approach	Time	Space	When to Use
Bitwise Shift and OR	O(32)	O(1)	General solution for interviews and coding platforms; easy to understand and implement
Bit Manipulation with Precomputed Masks	O(1)	O(1)	When optimizing bit operations or demonstrating advanced bit tricks

Frequently asked questions

Is Reverse Bits easy or hard?

Reverse Bits is classified as an Easy problem on most coding platforms. The core idea requires understanding basic bit operations such as masking and shifting. Once those concepts are clear, the implementation is straightforward.

Reverse Bits Python/Java solution

Python and Java solutions typically use the same loop-based technique. Iterate 32 times, shift the result left, append the current least significant bit using result |= (n & 1), and shift the input right. The logic remains identical across C++, Java, Python, and JavaScript.

How to solve Reverse Bits in O(1)?

An O(1) solution uses precomputed bit masks to swap groups of bits. The algorithm swaps 16-bit halves, then 8-bit blocks, then 4-bit, 2-bit, and 1-bit groups using masking and shifting operations. The number of operations is constant regardless of input value.

What is the best approach for Reverse Bits?

The most practical approach is the bitwise shift and OR method. Iterate through all 32 bits, extract the least significant bit using n & 1, shift the result left, and append the bit. This runs in O(32) time and O(1) space, which is effectively constant for a fixed-width integer.

Is Reverse Bits asked at Google/Amazon/Meta?

Reverse Bits appears frequently in technical interviews at companies that emphasize low-level problem solving, including Google, Amazon, and Meta. It tests understanding of bit manipulation, shifting operations, and binary representation of integers.

What data structure is used in Reverse Bits?

No complex data structure is required. The problem relies entirely on bit manipulation operations such as AND, OR, and bit shifts. The integer itself is treated as a sequence of bits that are processed or swapped.

What is the time complexity of Reverse Bits?

The typical solution runs in O(32) time because a 32-bit integer requires exactly 32 iterations. Since the number of bits is fixed, the runtime is effectively constant. Space complexity remains O(1) because only a few integer variables are used.

Reverse Bits solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Bitwise Shift and OR

Approach 2: Approach 2: Bit Manipulation with Precomputed Masks

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Reverse Bits solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Bitwise Shift and OR

Approach 2: Approach 2: Bit Manipulation with Precomputed Masks

Approach 3: Bit Manipulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems