Reverse Bits

Easy Problem 149 of 151 Java and Python

Practice on LeetCode

Problem

Reverse the bits of a given 32-bit unsigned integer n: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on.

In Java the input and output are ints holding the same 32 bits (they may print as negative numbers).

Example 1

Input: n = 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)

Example 2

Input: n = 1
Output: 2147483648 (in Java: -2147483648)
Why: The lowest bit becomes the highest.

Constraints

n is a 32-bit unsigned integer.

Explanation

Build the answer one bit at a time: shift the result left to make room, copy in the lowest bit of n, then shift n right. After 32 rounds, the first bit you read ends up at the top.

Approach 1 · Naive

Through a binary string

Time O(32)
Space O(32)

Write the number as a 32-character binary string, reverse it, and parse it back.

Format n as 32 binary digits with leading zeros.
Reverse the string and parse it as an unsigned number.

Java

class Solution {
    public int reverseBits(int n) {
        String bits = String.format("%32s", Integer.toBinaryString(n)).replace(' ', '0');
        return Integer.parseUnsignedInt(new StringBuilder(bits).reverse().toString(), 2);
    }
}

Python

class Solution:
    def reverseBits(self, n: int) -> int:
        return int(format(n, "032b")[::-1], 2)

Approach 2 · Optimal

Shift bits across

Time O(32)
Space O(1)

For 32 rounds, move the lowest bit of n into the result.

result = 0.
Repeat 32 times: result = (result << 1) | (n & 1); shift n right (unsigned in Java).
Return result.

Java

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

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

Complexity compared

Approach	Time	Space
Naive Through a binary string	O(32)	O(32)
Optimal Shift bits across	O(32)	O(1)

Key takeaways

Follow-up for repeated calls: precompute reversed bytes in a 256-entry table and combine four lookups.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem