algoadvance

Leetcode 190. Reverse Bits

Problem Statement

Reverse the bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string `00000010100101000001111010011100` represents the unsigned integer 43261596, so return 964176192 which its binary representation is `00111001011110000010100101000000`.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string `11111111111111111111111111111101` represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is `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 signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, you can assume that the input is always a 32-bit integer.

Clarifying Questions

1. Should the function handle the input as a string or directly as an integer?
   • It will handle the input as a 32-bit unsigned integer directly.
2. Are there any constraints on the input?
   • Yes, the input will always be a valid 32-bit unsigned integer.
3. Are we allowed to use built-in functions to convert between binary and integer representations, or do we have to do bit manipulation manually?
   • Bit manipulation should be used to achieve the reversal.

Strategy

To solve this problem, we need to reverse the bits of the given unsigned 32-bit integer. We can use bitwise operations to achieve this. Here is the step-by-step strategy:

1. Initialize the result res to 0.
2. Iterate through each of the 32 bits of the input integer.
3. In each iteration, left-shift the result to make space for the next bit.
4. Extract the least significant bit (LSB) of the input number and add it to the result.
5. Right-shift the input number to process the next bit in the next iteration.
6. Repeat this process until all 32 bits are processed.
7. Return the result.

Code

#include <stdint.h>

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

Time Complexity

The time complexity of this solution is (O(1)) because the loop always runs a fixed number of times (32 iterations), regardless of the input size.

The space complexity is also (O(1)) because we are only using a constant amount of additional space.

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?