Reverse Bits

easy
Bit ManipulationBit Manipulation

Reverse the bits of a given 32-bit unsigned integer. Return the integer formed by reversing the binary representation of the input, treating it as a full 32-bit value with leading zeros.

Examples

Example 1

  • Input: n = 00000010100101000001111010011100
  • Output: 964176192
  • Explanation: The input binary string 00000010100101000001111010011100 reversed is 00111001011110000010100101000000, which is 964176192 in decimal.

Example 2

  • Input: n = 11111111111111111111111111111101
  • Output: 3221225471
  • Explanation: The input binary string 11111111111111111111111111111101 reversed is 10111111111111111111111111111111, which is 3221225471 in decimal.

Constraints

  • The input must be a 32-bit unsigned integer.

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Loop Through All 32 Bits

Intuition

The most straightforward approach is to iterate through all 32 bit positions. For each position, we extract the least significant bit of the input, place it into the correct reversed position in the result, and shift the input right. We build the result by shifting it left before adding each new bit. After 32 iterations, the result holds the fully reversed value.

Algorithm

  1. Initialize `result` to `0`.
  2. Loop 32 times. In each iteration:
  3. Return `result`.
TimeO(1) — always exactly 32 iterationsSpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    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;
    }
};
Java 21
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;
    }
}
Python 3.12
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result
Go 1.26
func reverseBits(n int) int {
    u := uint32(n)
    var result uint32 = 0
    for i := 0; i < 32; i++ {
        result = (result << 1) | (u & 1)
        u >>= 1
    }
    return int(result)
}
Approach 2

Divide and Conquer with Masks

Intuition

We can reverse all 32 bits in O(log 32) = O(1) steps by swapping progressively smaller groups of bits. First swap the two 16-bit halves, then swap adjacent 8-bit groups within each half, then 4-bit nibbles, then 2-bit pairs, and finally individual adjacent bits. This uses pre-computed bitmasks and is highly efficient, performing only 5 shift-and-mask operations.

Algorithm

  1. Swap the top 16 bits and bottom 16 bits: `n = (n >> 16) | (n << 16)`.
  2. Swap adjacent 8-bit blocks using mask `0x00FF00FF`: `n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)`.
  3. Swap adjacent 4-bit nibbles using mask `0x0F0F0F0F`: `n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)`.
  4. Swap adjacent 2-bit pairs using mask `0x33333333`: `n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)`.
  5. Swap adjacent single bits using mask `0x55555555`: `n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)`.
  6. Return `n`.
TimeO(1) — exactly 5 operationsSpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16);
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
        return n;
    }
};
Java 21
class Solution {
    public int reverseBits(int n) {
        n = (n >>> 16) | (n << 16);
        n = ((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8);
        n = ((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1);
        return n;
    }
}
Python 3.12
class Solution:
    def reverseBits(self, n: int) -> int:
        n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
        return n
Go 1.26
func reverseBits(n int) int {
    u := uint32(n)
    u = (u >> 16) | (u << 16)
    u = ((u & 0xFF00FF00) >> 8) | ((u & 0x00FF00FF) << 8)
    u = ((u & 0xF0F0F0F0) >> 4) | ((u & 0x0F0F0F0F) << 4)
    u = ((u & 0xCCCCCCCC) >> 2) | ((u & 0x33333333) << 2)
    u = ((u & 0xAAAAAAAA) >> 1) | ((u & 0x55555555) << 1)
    return int(u)
}

Frequently asked questions

What is the optimal time complexity of Reverse Bits?

The most efficient approach in this guide ("Divide and Conquer with Masks") runs in O(1) — exactly 5 operations time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Reverse Bits use?

Reverse Bits is a easy-level Bit Manipulation problem involving Bit Manipulation. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Reverse Bits be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Number of 1 Bits

Original problem: leetcode.com

Loading editor...
Input
n=
0
Expected Output
0