Reverse Bits

Problem

Network protocols and signal-processing firmware sometimes require bit-reversal to adapt between big-endian and little-endian bit ordering. Given a 32-bit unsigned integer n, return the integer formed by reversing all 32 of its bits.

Input:  n = 43261596  (00000010100101000001111010011100)
Output: 964176192     (00111001011110000010100101000000)
 
Input:  n = 1         (00000000000000000000000000000001)
Output: 2147483648    (10000000000000000000000000000000)

Solution

Approach - Shift in from the right, shift out to the left, 32 times.

Build the answer one bit at a time. Each iteration does three things: read the current least-significant bit of n with n & 1, make room in the result by shifting it left one position with result << 1, then drop the read bit into that freed slot with | (n & 1). Finally n >>= 1 discards the bit just consumed so the next iteration sees a new LSB. The mechanism reverses the order because the first bit you pull out (n's bit 0) gets shifted leftward once on every subsequent iteration, so after 32 passes it has travelled all the way to position 31 - the MSB. The last bit pulled out never gets shifted again and stays at position 0.

Running exactly 32 times is what makes it a true 32-bit reversal: small inputs have leading zeros that must reverse into trailing zeros, so you cannot stop early when n hits 0. Trace n = 13 = 1101. Iteration 1: LSB is 1, result = (0 << 1) | 1 = 1, n becomes 110. Iteration 2: LSB is 0, result = (1 << 1) | 0 = 2, n becomes 11. Iteration 3: LSB is 1, result = (2 << 1) | 1 = 5, n becomes 1. The remaining iterations keep shifting result left, padding the low bits with the leading zeros of 13.

Edge cases - reverse_bits(0) stays 0 since no bit is ever set. The fixed 32-iteration count is what correctly maps a tiny input like 1 to 2147483648 = 2^31 instead of leaving it as 1.

Complexity - O(1) time, O(1) space - the loop always runs 32 iterations regardless of input, using only the result integer.