Reverse Bits (LeetCode 190)
You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.
For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.
Worked Examples
n = 4326159696417619243261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.n = 214748364410737418222147483644 is 01111111111111111111111111111100. Reversed, that reads 00111111111111111111111111111110, which is 1073741822.⚖️Formal Constraints & Bounds
0 <= n <= 231 - 2nis even.
Core Insight
For 32 iterations, shift res left by 1 and OR it with (n & 1), then right shift n by 1. Runs in exactly 32 steps with O(1) space.
Real-World Scenario & Production Applications
Endianness conversion in network protocols, Fast Fourier Transform (FFT) bit-reversal permutation, graphic rendering texture addressing.
Step-by-Step Execution Trace Table
Iteration i | Current n LSB (n & 1) | Shift res Left (res << 1) | Insert Bit (res \vert \text{bit}) | Shift n Right (n >> 1) | Bit Position Transferred |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | n >> 1 | Bit 0 transferred to Bit 31 |
| 2 | 0 | 10_2 | 10_2 | n >> 1 | Bit 1 transferred to Bit 30 |
| 3 | 1 | 100_2 | 101_2 | n >> 1 | Bit 2 transferred to Bit 29 |
| ... | ... | ... | ... | ... | Loop runs exactly 32 times |
| 32 | LSB of 32nd bit | Final shift | Full 32-bit reversed value | 0 | Bit 31 transferred to Bit 0 |
| 1 | res = 0 |
| 2 | for _ in range(32): |
| 3 | res = (res << 1) | (n & 1) |
| 4 | n >>= 1 |
| 5 | return res |
Conceptual Narrative
Reversing 32-bit unsigned integers converts bit-level streams by extracting bits from lowest to highest and shifting them into an accumulator in O(1) time.
🧭 Conceptual Foundation & Pattern Intuition
Reversing an integer's bits is identical to reversing decimal digits: pop the least significant unit and push it onto the result accumulator. In binary, "pop" is n & 1 followed by n >>= 1, and "push" is res = (res << 1) | bit. For high-throughput systems, divide-and-conquer bitmask swapping reverses 16-bit halves, 8-bit bytes, 4-bit nibbles, 2-bit pairs, and adjacent bits in 5 mask-and-shift steps without loops.
🏟️ The Analogy: The Conveyor Belts
Imagine two 32-slot conveyor belts. Belt A moves right, dropping its rightmost box into your hand. You place the box onto Belt B, which moves left. After exactly 32 steps, Belt B contains Belt A in exact reverse order.
🔑 Why It Works
Running exactly 32 fixed cycles guarantees that the leading zeros of n are shifted into res too, so every bit lands at its mirrored position.
Premature loop termination with
while n::while n:stops once the last 1-bit is read, son's leading zeros are never shifted intores:n = 2returns1instead of1073741824. Run exactly 32 rounds.In C, and in C++ before C++20, shifting a signed 32-bit
resinto bit 31 is undefined behavior: keepresinuint32_tthere. Python ints have no fixed width, so this does not apply to the Python solution.In C/C++, a shift by the full width (
x << 32on a 32-bit type) is undefined behavior: the shift count must be smaller than the type's width. The 32-round loop only ever shifts by 1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits": a fixed word size, and every bit moves to its mirrored position.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet; after 32 rounds bit i sits at bit 31 - i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
res = (res << 1) | (n & 1)shifts before it adds: OR-ing the bit in first and shifting after (res = (res | (n & 1)) << 1) moves every bit one place too far:n = 2returns2147483648, not1073741824.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Bit Tricks: I move bits with shifts and masks, never through a string. I start with
res = 0and run exactly 32 rounds. Each round shiftsresleft by one, drops the lowest bit ofninto the free slot withn & 1, and then shiftsnright. So the first bit I read climbs one place every round and ends at the top, and after 32 rounds bitiofnsits at bit31 - i. The rounds must be exactly 32: stopping whennhits zero would skip its leading zeros, son = 2would come out as1. That is 32 constant-time rounds,O(1)time, andO(1)space.
Complexity & Mathematical Proof
O(1)
Look at the execution steps: Fixed 32 iterations: at each step, shifts result left by 1, extracts lowest bit of input (n & 1), bitwise ORs into result, and shifts input right by 1. Always exactly 32 steps.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 32-bit integer result register in O(1) space.
Derivation Progression
res = (res << 1) | (n \& 1)
Pushes lowest bit of n into lowest position of res in O(1).
n >>= 1
Discards processed bit.
Fixed number of CPU instructions.
Variable Definitions
Fixed 32-bit unsigned integer word width
Memory Architecture & Bounds
O(1) Iterative
O(1) Single 32-bit register
O(1) Unsigned 32-bit integer
Boundary Best / Worst Cases
(32 fixed steps).
(32 fixed steps).
(32 fixed steps).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The statement says: "Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits". This is a pure bit-reversal permutation. There are two approaches: a bit-by-bit stream reversal (shifting bits one by one into a result register), or a divide-and-conquer parallel mask swap (swapping 16-bit halves, then 8-bit bytes, then nibbles, then pairs, then individual bits).
LeetCode gives n as an even integer with , read as 32 bits. Time complexity must be (exactly 32 iterations for loop, or 5 operations for divide-and-conquer). Space must be .
The primary trap is stopping when n == 0! If n has leading zeros (e.g. n = 2, which has 30 leading zeros), stopping when n == 0 reverses only the non-zero bits, outputting 1 instead of 2^{30} (). The loop must strictly run for all 32 positions.
Reverse Bits (LeetCode 190)
You are given an integer n. Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits, and return the number the reversed bits represent.
For example, 2 is 00000000000000000000000000000010; reversed it becomes 01000000000000000000000000000000, which is 1073741824.
Worked Examples
n = 4326159696417619243261596 is 00000010100101000001111010011100 in 32-bit binary. Reversed, that reads 00111001011110000010100101000000, which is 964176192.n = 214748364410737418222147483644 is 01111111111111111111111111111100. Reversed, that reads 00111111111111111111111111111110, which is 1073741822.⚖️Formal Constraints & Bounds
0 <= n <= 231 - 2nis even.
Core Insight
For 32 iterations, shift res left by 1 and OR it with (n & 1), then right shift n by 1. Runs in exactly 32 steps with O(1) space.
Real-World Scenario & Production Applications
Endianness conversion in network protocols, Fast Fourier Transform (FFT) bit-reversal permutation, graphic rendering texture addressing.
Step-by-Step Execution Trace Table
Iteration i | Current n LSB (n & 1) | Shift res Left (res << 1) | Insert Bit (res \vert \text{bit}) | Shift n Right (n >> 1) | Bit Position Transferred |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | n >> 1 | Bit 0 transferred to Bit 31 |
| 2 | 0 | 10_2 | 10_2 | n >> 1 | Bit 1 transferred to Bit 30 |
| 3 | 1 | 100_2 | 101_2 | n >> 1 | Bit 2 transferred to Bit 29 |
| ... | ... | ... | ... | ... | Loop runs exactly 32 times |
| 32 | LSB of 32nd bit | Final shift | Full 32-bit reversed value | 0 | Bit 31 transferred to Bit 0 |
| 1 | res = 0 |
| 2 | for _ in range(32): |
| 3 | res = (res << 1) | (n & 1) |
| 4 | n >>= 1 |
| 5 | return res |
Conceptual Narrative
Reversing 32-bit unsigned integers converts bit-level streams by extracting bits from lowest to highest and shifting them into an accumulator in O(1) time.
🧭 Conceptual Foundation & Pattern Intuition
Reversing an integer's bits is identical to reversing decimal digits: pop the least significant unit and push it onto the result accumulator. In binary, "pop" is n & 1 followed by n >>= 1, and "push" is res = (res << 1) | bit. For high-throughput systems, divide-and-conquer bitmask swapping reverses 16-bit halves, 8-bit bytes, 4-bit nibbles, 2-bit pairs, and adjacent bits in 5 mask-and-shift steps without loops.
🏟️ The Analogy: The Conveyor Belts
Imagine two 32-slot conveyor belts. Belt A moves right, dropping its rightmost box into your hand. You place the box onto Belt B, which moves left. After exactly 32 steps, Belt B contains Belt A in exact reverse order.
🔑 Why It Works
Running exactly 32 fixed cycles guarantees that the leading zeros of n are shifted into res too, so every bit lands at its mirrored position.
Premature loop termination with
while n::while n:stops once the last 1-bit is read, son's leading zeros are never shifted intores:n = 2returns1instead of1073741824. Run exactly 32 rounds.In C, and in C++ before C++20, shifting a signed 32-bit
resinto bit 31 is undefined behavior: keepresinuint32_tthere. Python ints have no fixed width, so this does not apply to the Python solution.In C/C++, a shift by the full width (
x << 32on a 32-bit type) is undefined behavior: the shift count must be smaller than the type's width. The 32-round loop only ever shifts by 1.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits": a fixed word size, and every bit moves to its mirrored position.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: after k rounds, res holds the lowest k bits of the original n in reverse order, and n holds the bits not read yet; after 32 rounds bit i sits at bit 31 - i.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
res = (res << 1) | (n & 1)shifts before it adds: OR-ing the bit in first and shifting after (res = (res | (n & 1)) << 1) moves every bit one place too far:n = 2returns2147483648, not1073741824.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Bit Tricks: I move bits with shifts and masks, never through a string. I start with
res = 0and run exactly 32 rounds. Each round shiftsresleft by one, drops the lowest bit ofninto the free slot withn & 1, and then shiftsnright. So the first bit I read climbs one place every round and ends at the top, and after 32 rounds bitiofnsits at bit31 - i. The rounds must be exactly 32: stopping whennhits zero would skip its leading zeros, son = 2would come out as1. That is 32 constant-time rounds,O(1)time, andO(1)space.
Complexity & Mathematical Proof
O(1)
Look at the execution steps: Fixed 32 iterations: at each step, shifts result left by 1, extracts lowest bit of input (n & 1), bitwise ORs into result, and shifts input right by 1. Always exactly 32 steps.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 32-bit integer result register in O(1) space.
Derivation Progression
res = (res << 1) | (n \& 1)
Pushes lowest bit of n into lowest position of res in O(1).
n >>= 1
Discards processed bit.
Fixed number of CPU instructions.
Variable Definitions
Fixed 32-bit unsigned integer word width
Memory Architecture & Bounds
O(1) Iterative
O(1) Single 32-bit register
O(1) Unsigned 32-bit integer
Boundary Best / Worst Cases
(32 fixed steps).
(32 fixed steps).
(32 fixed steps).
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
The statement says: "Write it as a 32-bit binary number (padding with leading zeros), reverse the order of those 32 bits". This is a pure bit-reversal permutation. There are two approaches: a bit-by-bit stream reversal (shifting bits one by one into a result register), or a divide-and-conquer parallel mask swap (swapping 16-bit halves, then 8-bit bytes, then nibbles, then pairs, then individual bits).
LeetCode gives n as an even integer with , read as 32 bits. Time complexity must be (exactly 32 iterations for loop, or 5 operations for divide-and-conquer). Space must be .
The primary trap is stopping when n == 0! If n has leading zeros (e.g. n = 2, which has 30 leading zeros), stopping when n == 0 reverses only the non-zero bits, outputting 1 instead of 2^{30} (). The loop must strictly run for all 32 positions.