LeetCode 190 · Easy · Bit Manipulation

Reverse Bits

Treat n as a 32-bit unsigned integer and return the number whose 32 bits are n's bits in reverse order: bit 0 becomes bit 31, bit 1 becomes bit 30, and so on.

O(32)time · O(1)
O(1)space
i → 31 − ishift, mask, OR

a whole number from 0 to 4294967295 (2³² − 1), or exactly 32 binary digits

n and res bit i of n is read (right band) and written into bit 31 − i of res (left band) · dim = not written yet

public int reverseBits(int n) { int res = 0; for (int i = 0; i < 32; i++) { int bit = (n >>> i) & 1; // read bit i res = res | (bit << (31 - i)); // write it at the mirror spot } return res;}
i
—
bit
—
31 − i
—
res
0

Why it works

  1. Brute force through strings: format n as a 32-character binary string (zero-padded!), reverse it and parse it back. Also O(32), but it allocates strings and hides the bit operations interviewers want to see.
  2. Read bit i, write bit 31 − i. (n >>> i) & 1 brings bit i down to position 0 and masks everything else away; bit << (31 − i) lifts it to its mirror position, and OR drops it into res without touching the bits already written.
  3. Always 32 rounds: leading zeros of n become trailing zeros of the answer, so the loop cannot stop early when n runs out of 1s. O(32) = O(1) time, O(1) space.
  4. Pitfall: signed shifts. Java has no unsigned int. >> copies the sign bit, so use >>> to read the bits of an n with bit 31 set. The returned int is negative when bit 31 of the answer is set; the page shows the same 32 bits as an unsigned number (Integer.toUnsignedString(res)).
  5. Follow-up, called many times: cache the reversal of each byte (a 256-entry table) and assemble four of them, or swap halves, then quarters, then pairs with masks: 5 steps instead of 32.