DSA SheetEasy
EditorialPractice

BIT MANIPULATION › BASIC BIT CONCEPTS

Reverse Bits

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A 32-bit word being reversed one bit at a timeThe figure shows two horizontal 32-bit rows. The input row has its least significant bit at the far right, and that bit is isolated first. Below it, the result row starts empty and grows from the left as it shifts left and receives each extracted bit on its right edge. The input shifts right after each extraction, so the bit read first travels to the result's far left after all 32 steps. This makes the opposite order visible, including zero bits.31|3029|2827|2625|2423|2221|2019|1817|1615|1413|1211|109|87|65|43|21|0least significant bit(read first)x >>= 1shift rightres <<= 1append bitb0|··|··|··|··|··|··|··|··|··|··|··|··|··|··|··|·x & 1append bitReverse a 32-bit word, one bit at a timeinput x — bit 0 is the least significant bit at the rightresult res — the first extracted bit becomes the MSB on the leftEach step reads x from the right, then shifts res left so the new bit is appended at theright.

Approach

  1. 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.
  2. 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.
  3. 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.
  4. Read x & 1 and combine it into res, because the least significant input bit is the next bit in the right-to-left scan.
  5. Shift x right by one position, because the next input bit must move into the least significant position before the next iteration.
  6. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraOnly 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);
    }
};

Common mistakeswrong shapes that look plausible in short tests

Previous · Count Total Set Bits