Skip to content

Volume ITechnology

4.30.4 — Reverse Bits ​

LeetCode 190 · Easy · ★ Blind 75

The problem ​

Reverse the bits of a 32-bit unsigned integer.

n = 00000010100101000001111010011100
  → 00111001011110000010100101000000

The pattern ​

Do it exactly 32 times, regardless of the value:

  • Take the lowest bit of n with n & 1.
  • Push it onto the result by shifting the result left and adding that bit.
  • Shift n right to expose the next bit.

The first bit taken ends up shifted left 31 times, so it lands at the top. The last bit taken stays at the bottom. That is the reversal.

The loop must run exactly 32 times, not until n becomes 0. Leading zeros in the input become trailing zeros in the output, and stopping early loses them. For n = 1 the answer is 2^{31}, not 1 — and a while n: loop would return 1.

That is the mistake people make in this problem, and it is easy to miss because the small test cases still pass.

The solution ​

python
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0  # (1)

        for _ in range(32):                 # (2) exactly 32, not "while n"
            result = (result << 1) | (n & 1)  # (3)
            n >>= 1  # (4)

        return result  # (5)
ts
function reverseBits(n: number): number {
  let result = 0;  // (1)

  for (let i = 0; i < 32; i++) {  // (2)
    result = (result << 1) | (n & 1);  // (3)
    n >>>= 1;                               // (4) UNSIGNED shift
  }

  return result >>> 0;                      // (5) reinterpret as unsigned
}

Line by line ​

(1) The reversed number is built up here.

(2) Exactly 32 rounds, one per bit. Stopping when n reaches 0 would be wrong, because the leading zeros of n must become trailing zeros of the answer, and they still need to be shifted in.

(3) Take the last bit of n and put it on the end of result. result << 1 shifts result one place left, making room. n & 1 is the last bit of n. | (OR) drops that bit into the free space. So the first bit taken from the right of n ends up furthest to the left in result.

(4) Drop the last bit of n, so the next round reads the next bit. In TypeScript, >>> is the unsigned right shift. The ordinary >> would copy the sign bit in from the left on numbers with the top bit set, and the loop would read the wrong bits.

(5) The reversed number. In TypeScript, bit operations work on signed 32-bit numbers, so a result with the top bit set would come out negative. >>> 0 reinterprets it as an unsigned number.

(result << 1) | (n & 1) in one expression. Shift the accumulated answer up to make room, then place the new bit at the bottom.

In TypeScript, >>> not >>. Bitwise operators coerce to 32-bit signed integers, so >> on a value with the top bit set drags 1s down from the left and the loop never terminates correctly. >>> shifts in zeros.

The final >>> 0 reinterprets the result as unsigned, because << may have produced a negative number. Without it, an answer above 2^{31} prints as negative.

Python has no such issue with >> on a non-negative value, but note that result will simply be a large positive integer rather than a fixed-width one.

Trace ​

Reversing the 4-bit value 1011 (illustrative — the real problem uses 32):

stepn & 1result beforeresult aftern after
1101101
2111110
30111101
4111011010

1011 reversed is 1101 ✓.

Edge cases ​

  • n = 0. All 32 zeros reverse to 0.
  • Only the lowest bit set, n = 1. It becomes the highest bit, 2^{31} = 2,147,483,648. In TypeScript, >>> 0 is what keeps that from showing as a negative number.

Complexity ​

O(1) — always 32 iterations. O(1) space.

The follow-up: many calls ​

The problem asks what you would do if the function were called millions of times.

Cache the reversal of each byte. Reverse each of the four bytes with a 256-entry lookup table, then reassemble them in the opposite order:

python
cache = {}
def reverseByte(b):
    if b not in cache:
        r, x = 0, b                     # work on a copy, so b stays the key
        for _ in range(8):
            r = (r << 1) | (x & 1)
            x >>= 1
        cache[b] = r
    return cache[b]

Four lookups instead of 32 iterations, with 256 entries of memory. This is memoisation applied to a bit operation, and it is the same trade as any cache: space for time, worth it only when the function is hot.

There is also a divide-and-conquer version that swaps adjacent bits, then pairs, then nibbles, then bytes — five masked shift-and-or steps with no loop at all:

python
n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)   # swap adjacent bits
n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)   # swap pairs
n = ((n >> 4) & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4)   # swap nibbles
n = ((n >> 8) & 0x00FF00FF) | ((n & 0x00FF00FF) << 8)   # swap bytes
n = (n >> 16) | (n << 16)                               # swap halves

Each mask selects alternating groups of a given size. Beautiful, and impossible to reconstruct from memory — name it, do not write it unless asked specifically.

Where this goes next ​

  • Number of 1 Bits — the same bit-by-bit walk, counting instead of reversing. 4.30.2.
  • Reverse Integer — the decimal version, with an overflow check. 4.30.7.
  • Byte-order swapping — htonl and friends swap byte order for network transmission, using the same masked shifts. Chapter 5.9 covers why network byte order exists.
  • Bit-reversal permutation — the FFT reorders its input by reversing the bit pattern of each index, which is this operation used in earnest.

What the interviewer will push on ​

"Why exactly 32 iterations?" Leading zeros must become trailing zeros. Give n = 1 → 2^{31}.

"Why >>> in JavaScript?" >> is a signed shift and drags 1s in from the left.

"What if it is called millions of times?" A byte lookup table — four lookups instead of 32 steps.

"Can you do it without a loop?" The five-step masked swap. Say it exists.

"Where does this appear in real code?" Network byte order, and the FFT's bit-reversal permutation.

One thing to volunteer: name the 32-iteration trap before writing the loop. It is the only thing this problem is testing, and stating it first is worth more than the code.

Next: 4.30.5 Missing Number — XOR again, this time cancelling indices against values.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet