algoadvance

Leetcode 190. Reverse Bits

Problem Statement

Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string `00000010100101000001111010011100` is represented as the unsigned integer `43261596`, so the function should return `964176192`, which is the binary representation of `00111001011110000010100101000000`.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string `11111111111111111111111111111101` is represented as the unsigned integer `4294967293`, so the function should return `3221225471`, which is the binary representation of `10111111111111111111111111111111`.

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, you can assume that the input is always a 32 bits integer.

Clarifying Questions

1. Can we assume that the input provided to the function is always a valid 32-bit unsigned integer?
   • Yes.
2. Do we need to handle additional edge cases like inputs less than 32 bits?
   • No, the input is always exactly 32-bit.

Strategy

1. Initialize the result to 0.
2. Iterate over each bit position from 0 to 31.
3. Extract the least significant bit from the input number.
4. Left shift the result to make space for the new bit.
5. Add the extracted bit to the result.
6. Right shift the input number to process the next bit.
7. Return the reversed result.

Code

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            // Extract the least significant bit of n
            int bit = n & 1;
            
            // Left shift the result to make space for the new bit
            result <<= 1;
            
            // Add the bit to the result
            result |= bit;
            
            // Right shift n to process the next bit
            n >>= 1;
        }
        return result;
    }
}

Time Complexity

• Time Complexity: O(1). The loop runs exactly 32 times regardless of the input, so the time complexity is constant.
• Space Complexity: O(1). We are using a constant amount of extra space for the result and bit variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?