Reverse Bits

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

Reverse Bits. Given a thirty-two bit unsigned integer, reverse the order of its bits and return the new number.

Start small, with eight bits: zero zero zero zero one zero one one, which is eleven. Backwards: one one zero one zero zero zero zero, or two hundred eight. The real input is the same, with thirty-two bits.

The easy way: turn the number into a binary string, pad it to thirty-two characters, reverse it, and parse it back. It works, but it builds strings when the bits are already right there.

Instead, picture two tracks of carts. Each step, the last cart rolls off n. The result track shifts left to make room, and the cart joins on the right. The first bit out ends up furthest left, so the order flips.

In code, loop thirty-two times. Shift result left, then OR in n and one, the lowest bit of n. Then shift n right, so the next bit is last. Finally, return result.

Let's run eleven. Out comes a one: result is one. Another one: one one. A zero: one one zero. Then a one: one one zero one. The last four are zeros; each just shifts left. Two hundred eight! The real input takes the same thirty-two steps.

Always thirty-two steps, so the time is O of one, and we keep two numbers, so the space is O of one. Bonus: masks can swap halves, then quarters, down to single bits, in just five rounds.

Last bit out, shifted in, thirty-two times. That's Reverse Bits.