Reverse Bits — Editorial

Opening the reading…

Intuitionthe fixed width matters more than the numeric value

A 32-bit number is a row of exactly 32 positions, even when its usual decimal or binary notation does not show leading zeroes. Reversing the bits means position 0 moves to position 31, position 1 moves to position 30, and so on. Therefore, you must process all 32 positions, not only the positions containing a 1.

The least significant bit is the next bit you can read from the input. Take it with x & 1, then shift the input right so the following bit becomes accessible. At the same time, shift the result left to open its next position and place the extracted bit there. Repeating this exactly 32 times makes the first bit read become the last bit written.

Approach

Copy n into an unsigned 32-bit value x, because right-shifting an unsigned value fills the left side with zeroes and keeps the bit operations predictable.

Start res at zero and repeat the same operation 32 times, because leading zeroes are part of the 32-bit representation and must also be reversed.

Shift res left by one position before inserting the next bit, because this moves every bit already collected toward its final position and leaves the rightmost position open.

Read x & 1 and combine it into res, because the least significant input bit is the next bit in the right-to-left scan.

Shift x right by one position, because the next input bit must move into the least significant position before the next iteration.

Return res as an int after all 32 positions have been written, because the requested interface returns the complete reversed 32-bit pattern rather than a partially built value.

Complexitythe width is fixed at 32 bits

MEASURE	BOUND	WHY
Time	O(32) = O(1)	The loop performs one extraction, one left shift, one right shift, and one insertion for each of the 32 positions. The work is fixed by the integer width, so no bit is processed twice and the bound does not grow with the numeric value of n.
Space	O(1) extra	Only x, res, and the loop counter are working variables. The returned integer is required output and is excluded from extra space; because every input has the same 32-bit width, there is no worse input shape that increases this bound.

The problem always processes exactly 32 bit positions, so no additional variable is needed to describe the bound.

Annotated solutionC++ · iterative bit scan · the direct version to remember

CPPRead the low bit 32 times and append each bit to the left-shifting result.

#include <cstdint>

using namespace std;

class Solution {
public:
    int reverseBits(int n) {
        unsigned int x = static_cast<unsigned int>(n);
        unsigned int res = 0;

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

        return static_cast<int>(res);
    }
};

The order of the two shifts is the central detail. res <<= 1 happens before the new bit is inserted, so the bit read on the first iteration eventually travels through 31 later shifts and reaches the result's most significant position. The unsigned copy makes x >>= 1 a logical shift, which fills newly exposed positions with zeroes.

The divide-and-conquer alternativea constant-time rearrangement that reduces the fixed number of stages

You can reverse the word in groups instead of reading one bit at a time. First swap the two 16-bit halves, then swap neighboring 8-bit groups, then neighboring 4-bit groups, then 2-bit groups, and finally individual bits. Masks keep each group in place while shifts exchange the groups. This is an optimization in the number of stages, not a change in asymptotic complexity: both methods are constant time for a 32-bit integer.

CPPSwap equal-sized groups from 16 bits down to 1 bit until the whole word is reversed.

#include <cstdint>

using namespace std;

class Solution {
public:
    int reverseBits(int n) {
        unsigned int x = static_cast<unsigned int>(n);

        x = (x >> 16) | (x << 16);
        x = ((x & 0xff00ff00u) >> 8) |
            ((x & 0x00ff00ffu) << 8);
        x = ((x & 0xf0f0f0f0u) >> 4) |
            ((x & 0x0f0f0f0fu) << 4);
        x = ((x & 0xccccccccu) >> 2) |
            ((x & 0x33333333u) << 2);
        x = ((x & 0xaaaaaaaau) >> 1) |
            ((x & 0x55555555u) << 1);

        return static_cast<int>(x);
    }
};