Reverse Bits

EASY

Description

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?

Approaches

Checkout 3 different approaches to solve Reverse Bits. Click on different approaches to view the approach and algorithm in detail.

String Conversion and Reversal

This approach is conceptually straightforward. It involves converting the 32-bit integer into its binary string representation, reversing this string, and then parsing the reversed string back into an integer.

Algorithm

Convert the integer n to its binary string representation using Integer.toBinaryString(n).
Pad the resulting string with leading zeros to ensure it has a length of 32.
Create a StringBuilder with this 32-bit string.
Reverse the StringBuilder.
Convert the reversed StringBuilder back to a string.
Parse the reversed binary string. Since the value might exceed Integer.MAX_VALUE, parse it as a long using Long.parseLong(string, 2) and then cast the result to an int.

The core idea is to leverage built-in string manipulation functions. First, we need to get the 32-bit binary representation of the input integer n. Standard library functions like Integer.toBinaryString(n) do not produce a 32-bit string with leading zeros, so manual padding is required. Once we have the 32-bit string, we can use a StringBuilder to reverse it efficiently. Finally, the reversed binary string needs to be converted back to an integer. Since the reversed string can represent a number larger than Integer.MAX_VALUE (e.g., if the original LSB was 1, the new MSB will be 1, making it a large positive or negative number in signed context), it's safer to parse it as a long and then cast it to an int. This correctly handles the unsigned nature of the problem within Java's signed integer context.

public class Solution {
    // you need to treat n as an unsigned value
    public int reverseBits(int n) {
        String binaryString = Integer.toBinaryString(n);
        
        // Pad with leading zeros to make it 32 bits long
        while (binaryString.length() < 32) {
            binaryString = "0" + binaryString;
        }
        
        StringBuilder reversedBuilder = new StringBuilder(binaryString);
        reversedBuilder.reverse();
        
        // Use Long.parseLong to handle unsigned values that would overflow a signed int
        // when the most significant bit is 1.
        long resultAsLong = Long.parseLong(reversedBuilder.toString(), 2);
        return (int) resultAsLong;
    }
}

Complexity Analysis

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

Pros and Cons

Pros:

Easy to understand and implement for those more familiar with string manipulation than bitwise operations.
Leverages high-level, built-in library functions.

Cons:

Significantly less performant than bitwise approaches due to the overhead of string object creation, manipulation, and parsing.
Requires careful handling of padding and type conversion to correctly simulate unsigned 32-bit integer behavior in Java.

Code Solutions

Checking out 4 solutions in different languages for Reverse Bits. Click on different languages to view the code.

public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n ) { int res = 0 ; for ( int i = 0 ; i < 32 && n != 0 ; ++ i ) { res |= (( n & 1 ) << ( 31 - i )); n >>>= 1 ; } return res ; } }

Video Solution

Watch the video walkthrough for Reverse Bits

Algorithms:

Divide and Conquer

Patterns:

Bit Manipulation

Companies:

Airbnb |Nvidia |Qualcomm |