Reverse Bits

Brute Force#

Convert the integer to its 32-bit binary string representation, pad with leading zeros to ensure full 32-bit width, then reverse the string and parse it back to an integer with base-2 conversion. This is conceptually simple but involves string allocation and string-to-integer parsing overhead — all unnecessary when direct bit manipulation can do the same in a tight loop.

class Solution {
public:
    int reverseBits(int n) {
        if (n==0)
            return 0;
        string bit;
        while (n>0) {
            bit = (n % 2 ==0 ? "0" : "1") + bit;
            n /= 2;
        }
        while (bit.length()<32)
        {
            bit = "0"+bit;
        }
        reverse(bit.begin(),bit.end());
        int num = stoi(bit, nullptr, 2);
        return num;
    }
};

Bit Manipulation#

In each of 32 iterations, shift the result left by 1 to make room for the next bit, OR the least-significant bit of n into the result, then shift n right. Essentially, bits are read from n LSB-first and written into res LSB-first — which reverses their order. This runs in a fixed 32 iterations with O(1) space and no string conversion.

class Solution {
public:
    int reverseBits(int n) {
        uint32_t res = 0;

        for(int i=0;i<32;i++)
        {
            res = res << 1;
            res = res | (n&1);
            n = n >> 1;
        }
        return res;
    }
};

Time Complexity: O(32) ~ O(1)

Space Complexity: O(1)