Reverse Bits

easy bit manipulation

Problem

Reverse bits of a given 32 bits unsigned integer.

Inputn = 0b00000010100101000001111010011100

Output0b00111001011110000010100101000000

Loop 32 times. Each step shifts the answer left, ORs in the lowest bit of n, then shifts n right.

n (decimal, 0 ≤ n < 2^32)

def reverse_bits(n):
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

function reverseBits(n) {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n = n >>> 1;
  }
  return result >>> 0;
}

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

uint32_t reverseBits(uint32_t n) {
    uint32_t result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1u);
        n >>= 1;
    }
    return result;
}

Explanation

To reverse the bits of a 32-bit number, we peel off n's bits from the right and stack them onto result from the left. Doing this 32 times produces the mirror image.

Each iteration does two things. We grab the lowest bit of n with n & 1, then build the answer with result = (result << 1) | (n & 1) — shifting result left makes room, and the OR drops the new bit into the now-empty lowest slot.

After using that bit, we discard it with n >>= 1, sliding n right so the next bit becomes the new lowest.

Because the first bit we read ends up shifted left the most, it lands in the highest position of the result — which is exactly what reversing means.

Example: with bits ...1011, the first read bit 1 gets pushed left through all 32 shifts and ends up near the top, while later bits stay lower. After 32 rounds, result holds the fully reversed bit pattern.

Time: O(32) = O(1) Space: O(1)