Skip to content

Volume ITechnology

4.30.0 — Bit Manipulation: The Pattern ​

Recognition cue. The problem says "without extra memory", "appears once", "count the bits", "without using +", or the constraints mention 32-bit integers. Small subsets (n ≤ 20) also point here, via bitmasks.

The five operators, and what each is for ​

operatordoesuse it to
&1 only where both are 1test a bit, clear bits
|1 where either is 1set a bit, merge two sets
^1 where they differtoggle a bit, cancel pairs
~flips every bitbuild a mask
<< >>shift left / rightmultiply or divide by 2, build a mask

They stop feeling like arithmetic if you read a number as a set. Each bit position is one possible member, and a 1 means "this member is in the set". Then & keeps the members that are in both sets, which is called the intersection. | keeps the members that are in either set, which is the union. ^ keeps the members that are in exactly one of the two sets, which is the symmetric difference.

The four idioms worth memorising ​

python
x & (1 << i)          # is bit i set?
x |= (1 << i)         # set bit i
x &= ~(1 << i)        # clear bit i
x ^= (1 << i)         # toggle bit i

x & (x - 1)           # clear the LOWEST set bit
x & -x                # isolate the lowest set bit
x & 1                 # is x odd?
x >> 1                # x // 2  (for non-negative x)

Reading the cheat sheet, line by line. 1 << i is a number with only bit i set. For i = 3 that is binary 1000, which is 8. Every line on the first four rows uses it as a mask, a number that picks out one bit.

  • x & (1 << i) keeps only bit i of x. A non-zero result means that bit is set.
  • x |= (1 << i) turns bit i on and leaves the rest alone, because OR with 0 changes nothing.
  • x &= ~(1 << i) turns bit i off. ~ flips every bit of the mask, so it has a 0 only at position i, and AND with it clears just that bit.
  • x ^= (1 << i) flips bit i, because XOR with 1 flips a bit and XOR with 0 leaves it.
  • x & (x - 1) removes the lowest set bit. Subtracting 1 turns that bit to 0 and every 0 below it to 1, so AND keeps everything except that bit. It is the engine of 4.30.2.
  • x & -x keeps only the lowest set bit. In two's complement, -x is "flip every bit, then add 1", which leaves the lowest set bit as the only bit the two share.
  • x & 1 is the last bit, so it is 1 exactly when x is odd.
  • x >> 1 shifts every bit one place right, which halves x and rounds down.

x & (x - 1) is the one to understand rather than memorise. Subtracting 1 flips the lowest set bit to 0 and turns every 0 below it into 1. ANDing with the original keeps only the bits above, so the lowest set bit is gone.

x       = 1011 0100
x - 1   = 1011 0011      ← lowest 1 became 0, the zeros below became 1
x & (x-1) = 1011 0000    ← that bit cleared

Two consequences: counting set bits by looping until zero (Brian Kernighan's method), and testing for a power of two with x > 0 and x & (x - 1) == 0.

x & -x isolates it instead of clearing it, because -x is ~x + 1 in two's complement, which flips everything above the lowest set bit and leaves that bit alone. It is how Fenwick trees find their next index (4.13.4).

XOR: the three properties ​

XOR carries most of this chapter, and everything follows from three facts:

x \oplus x = 0 \qquad x \oplus 0 = x \qquad \text{XOR is commutative and associative}

So XOR-ing a list cancels every value that appears an even number of times, regardless of order. That single sentence solves Single Number, Missing Number, and finding a duplicate in a range.

XOR is also addition without carrying, which is why it appears inside Sum of Two Integers.

Bitmasks as sets ​

A subset of up to about 20 items fits in one integer, one bit per item.

python
for mask in range(1 << n):            # every subset of n items
    for i in range(n):
        if mask & (1 << i):           # is item i in this subset?
            ...

1 << n is 2^n. This is 4.18.1 Subsets done with integers, and it is the gateway to bitmask DP, where a subset becomes a DP state (4.29).

The language traps ​

Python integers are unbounded and negatives have infinitely many leading 1s. ~5 is -6, not a 32-bit pattern. To work in 32-bit arithmetic you must mask: x & 0xFFFFFFFF, and convert back to a signed value at the end. This is the single biggest source of confusion in Python bit problems, and 4.30.6 is where it bites.

JavaScript's bitwise operators coerce to 32-bit signed integers, even though numbers are otherwise doubles. So >> gives a signed shift and >>> gives an unsigned one — and using the wrong one on a value with the top bit set gives a negative result.

Java has >>> too, for the same reason. C and C++ leave shifting a signed negative value undefined. Know your language before claiming a bit trick is portable.

The seven problems ​

#ProblemThe one insight
4.30.1Single Number ★XOR cancels every pair
4.30.2Number of 1 Bits ★x & (x-1) clears the lowest set bit
4.30.3Counting Bits ★bits[i] = bits[i >> 1] + (i & 1)
4.30.4Reverse Bits ★Pull from the right, push to the left
4.30.5Missing Number ★XOR the indices with the values
4.30.6Sum of Two Integers ★XOR is the sum, AND-shifted is the carry
4.30.7Reverse IntegerCheck overflow before it happens

★ marks the Blind 75 subset.

What the interviewer will push on ​

"Explain x & (x-1)." Borrowing flips the lowest 1 and sets everything below it; the AND keeps only the bits above.

"Why does XOR solve this?" x ^ x = 0, and order does not matter.

"What does two's complement do to -x?" It is ~x + 1, which is why x & -x isolates the lowest set bit.

"Does this work in Python?" Only with masking — Python integers have no fixed width.

"How would you count set bits fastest?" x & (x-1) in a loop is O(\text{set bits}); a lookup table is O(1) per byte; and every modern CPU has a popcount instruction that the compiler will emit.

One thing to volunteer: read the operators as set operations. "& is intersection, | is union, ^ is symmetric difference." It makes bitmask problems obvious instead of cryptic.

Recall

  • Read the operators as sets: & intersection, | union, ^ symmetric difference.
  • XOR: x ^ x = 0, x ^ 0 = x, order does not matter. So XOR-ing a list cancels everything appearing an even number of times.
  • x & (x-1) clears the lowest set bit — count bits with it, and test a power of two with x > 0 and x & (x-1) == 0.
  • x & -x isolates the lowest set bit, because -x is ~x + 1.
  • 1 << n is 2^n; iterate range(1 << n) to enumerate every subset of n items.
  • Python integers are unbounded — mask with 0xFFFFFFFF to simulate 32 bits, and convert back to signed at the end.
  • JavaScript bitwise operators coerce to 32-bit signed; use >>> for an unsigned shift.
  • Check overflow before performing the operation, not after.

Next: 4.30.1 Single Number — the cleanest use of XOR there is.

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