4.29 — Bit Manipulation, Probabilistic Structures & NP-Hardness in Practice

Three topics that do not fit anywhere else and all show up in real work: the tricks that operate on the bits Chapter 1.3 built, the structures that answer questions approximately when exactly is too expensive, and the honest answer to "this problem has no fast algorithm".

1. Bit manipulation: the operations and what they are for

Chapter 1.3 covered binary and two's complement. Here are the operations and the idioms.

Operation	Symbol	Effect
AND	&	1 only where both are 1 — used to test and clear
OR	|	1 where either is 1 — used to set
XOR	^	1 where they differ — used to toggle and to cancel
NOT	~	flips every bit
Left shift	<<	x << k multiplies by 2^k
Right shift	>>	x >> k divides by 2^k, keeping the sign
Unsigned right shift	>>>	same but fills with zeros (JavaScript only)

The idioms worth memorising, each with what it is for:

x & (1 << k)          // is bit k set?          → non-zero if yes
x | (1 << k)          // set bit k
x & ~(1 << k)         // clear bit k
x ^ (1 << k)          // toggle bit k
x & (x - 1)           // clear the LOWEST set bit          ← (1)
x & -x                // isolate the LOWEST set bit        ← (2)
x & (x - 1) ? 'no' : 'power of two'                        // (3)

1. Subtracting 1 flips the lowest set bit to 0 and turns everything below it to 1s; ANDing therefore removes exactly that bit. Looping x &= x - 1 until zero counts the set bits in as many steps as there are 1 bits, not 32 — this is Brian Kernighan's algorithm.
2. In two's complement -x is ~x + 1, and ANDing isolates the lowest set bit. This is the Fenwick tree's engine from Chapter 4.13.4.
3. A power of two has exactly one set bit, so clearing the lowest leaves zero. Watch the x = 0 case, which this test wrongly accepts.

XOR's cancellation property is the one that solves puzzles. Three facts: a ^ a = 0, a ^ 0 = a, and XOR is commutative and associative. Together they mean XOR-ing a list cancels every value that appears an even number of times:

function singleNumber(nums: number[]): number {
  return nums.reduce((acc, n) => acc ^ n, 0);      // (1)
}

1. Every number appearing twice cancels to 0, leaving only the one that appears once. O(n) time, O(1) space — versus a hash map's O(n) space. This is the tell for a whole family of "find the odd one out" problems.

Bitmasks as sets. An integer can represent a subset of up to about 30 items in JavaScript (bitwise operators work on 32-bit signed integers, so bit 31 is the sign — Chapter 1.3). Bit i set means item i is in the set:

const has  = (mask: number, i: number) => (mask & (1 << i)) !== 0;
const add  = (mask: number, i: number) => mask | (1 << i);
const size = (mask: number) => { let c = 0; while (mask) { mask &= mask - 1; c++; } return c; };

This makes subset enumeration trivial — loop for (let m = 0; m < (1 << n); m++) and each m is one subset — and it is what powers bitmask DP from Chapter 4.22. The travelling salesman problem with state (currentCity, visitedMask) has n \cdot 2^n states, giving O(2^n n^2) instead of O(n!): for n = 20 that is 400 million instead of 2.4 \times 10^{18}.

Where bit tricks are genuinely used in production: permission flags packed into one integer, Bloom filters below, chess engines representing the board as 64-bit bitboards (one bit per square, so "all legal knight moves" is a shift and a mask), compression, and hash mixing (Chapter 4.3's FNV).

Where they are not: almost everywhere else. x >> 1 instead of x / 2 in application code makes it harder to read and the compiler already does that transformation. Use bit tricks where they are the meaning — a set of flags, a bitboard — not as a micro-optimisation.

2. Bloom filters: "definitely not" for almost no memory

You have a billion known-bad URLs and every page load must check against them. A hash set holds the URLs themselves — around 50 GB. Too much.

A Bloom filter answers "have I seen this?" in constant time and constant memory per item, with one specific compromise: it can say maybe yes when the answer is no, but it can never say no when the answer is yes.

The mechanism is a bit array plus k hash functions:

class BloomFilter {
  private bits: Uint8Array;
  constructor(private size: number, private k: number) {          // (1)
    this.bits = new Uint8Array(size);
  }
  private positions(item: string): number[] {
    return Array.from({ length: this.k }, (_, i) => hash(item, i) % this.size);   // (2)
  }
  add(item: string): void   { for (const p of this.positions(item)) this.bits[p] = 1; }   // (3)
  mayContain(item: string): boolean {
    return this.positions(item).every(p => this.bits[p] === 1);   // (4)
  }
}

1. size bits and k hash functions — the two tuning knobs.
2. Each item maps to k positions. In practice you derive all k from two hashes rather than computing k independent ones.
3. Adding sets those k bits to 1. The item itself is never stored, which is the whole memory saving.
4. If any of the k bits is 0, the item was definitely never added — because adding it would have set that bit. If all k are 1, it was probably added, or the bits happen to have been set by other items.

Why there are no false negatives: bits are only ever set, never cleared. A bit that was set for an item stays set forever, so the "all k bits are 1" check can never fail for something genuinely present. That one-directional guarantee is what makes the structure usable.

Sizing. For a false-positive rate p with n items, the optimal bit count and hash count are

m = -\frac{n \ln p}{(\ln 2)^2}, \qquad k = \frac{m}{n} \ln 2

The practical version to remember: about 10 bits per item gives roughly a 1% false-positive rate, at 7 hash functions. A billion URLs then need about 1.2 GB instead of 50 GB.

The failure mode. As it fills, every bit trends toward 1 and the false-positive rate climbs — and there is no signal. It does not throw, it just quietly starts saying "maybe" to everything. You must size for the expected item count up front and monitor the fill ratio.

Deletion is impossible, because clearing a bit might break a different item that shares it. A counting Bloom filter stores small counters instead of bits, which allows deletion at four times the memory. A cuckoo filter supports deletion and is often smaller at the same error rate.

The design test, which is the real skill: what does a false positive cost? If the answer is "one extra lookup in the real store", a Bloom filter is excellent. If the answer is "we charged the wrong customer", it is unusable. Chapter 10.18 works through this properly.

Where they are actually used: databases skipping files that cannot contain a key (Cassandra and every LSM engine — Chapter 7.3), CDNs deciding whether an object is worth caching, browsers checking malicious URLs, and Bitcoin's light clients.

3. Count-Min Sketch and HyperLogLog, briefly

Count-Min Sketch answers "roughly how many times have I seen this item?" over a stream too large to store counts for. It is a 2-D array of counters with one hash function per row; adding increments one counter per row, and querying takes the minimum across rows. The minimum is taken because collisions can only ever push a counter up, so the smallest of the k readings is the least contaminated. It over-estimates and never under-estimates. Used for heavy-hitter detection: which IPs are flooding us, which products are trending.

HyperLogLog answers "how many distinct items have I seen?" using around 12 KB for a cardinality estimate within about 2% — regardless of whether the true count is a thousand or a billion. The idea: hash each item and track the longest run of leading zeros seen. A run of 10 zeros suggests roughly 2^{10} distinct items, because that pattern has probability 2^{-10}. Averaging many such estimates across buckets tightens it.

The property that actually matters is mergeability, and it is worth stating clearly because people focus on the compression instead. Exact daily unique-visitor counts cannot be summed into a monthly figure — a visitor on Monday and Tuesday would be counted twice. HyperLogLog sketches merge by taking the maximum per bucket, so you can store one sketch per day and combine any range of days on demand. That is why every analytics system uses them.

4. NP-hardness: what it means and what to do about it

Chapter 1.7 built the theory. Here is the working version.

P is the set of problems solvable in polynomial time. NP is the set where a proposed solution can be checked in polynomial time. Every P problem is in NP — if you can solve it fast you can check it fast — and whether the reverse holds is the famous open question.

NP-complete problems are the hardest in NP: a fast algorithm for any one of them gives a fast algorithm for all of them. NP-hard means at least as hard as those, without necessarily being in NP itself.

What it means in practice: nobody knows a polynomial algorithm, thousands of very good people have tried since 1971, and you are not going to find one in an interview. The correct move is to recognise the problem and pivot to what you can do.

The ones you will actually meet:

• Travelling salesman — shortest route visiting every city once. Delivery routing.
• Knapsack (0/1) — Chapter 4.22. Pseudo-polynomial: the DP is O(nW), which is fast when the capacity W is small but exponential in the number of bits used to write W.
• Bin packing — fit items into the fewest containers. Server allocation, cutting stock.
• Graph colouring — assign colours with no two neighbours matching. Register allocation in compilers (Chapter 3.1), exam timetabling.
• Set cover — cover everything with the fewest sets. Sensor placement, test selection.
• Boolean satisfiability (SAT) — the original NP-complete problem, and now the surprise of the field: modern SAT solvers routinely handle instances with millions of variables, so "NP-complete" and "unsolvable in practice" are not the same statement.
• Longest simple path and subset sum — both appear as innocent-looking interview questions.

The five things to do instead of finding a polynomial algorithm:

Exponential but smart. Bitmask DP takes TSP from O(n!) to O(2^n n^2), which is fine up to about 20 cities. Branch and bound prunes aggressively using a lower bound.

Approximation with a proven ratio. Greedy set cover is never worse than \ln n times optimal, and that is provably the best possible unless P = NP. Metric TSP has a 1.5-approximation (Christofides). A guaranteed ratio is a real deliverable — "never more than 50% worse than optimal, computed in a second" is often the right business answer.

Heuristics with no guarantee. Simulated annealing, genetic algorithms, local search. No bound, but they routinely produce near-optimal answers on real instances. Most production routing software is here.

Exploit the structure of your actual instances. Real graphs are sparse, real scheduling problems have few distinct durations, real bin-packing has items far smaller than the bins. Many NP-hard problems are easy on the inputs that actually occur — graph colouring is hard in general and trivial on an interval graph.

Change the problem. Ask whether you need the true optimum. "Assign these 500 deliveries to 20 vans, minimising total distance" is NP-hard; "assign them so no van exceeds 8 hours" is a feasibility question a solver handles easily. Relaxing an optimisation into a constraint-satisfaction problem is the single most useful move here, and it is a product conversation as much as an engineering one.

What the interviewer will push on

"Count the set bits in an integer." The loop over 32 positions works. x &= x - 1 counting only the set bits is the better answer, and explaining why it clears exactly the lowest set bit is the point. Then mention that most CPUs have a popcount instruction and most languages expose it.

"Every number appears twice except one. Find it in O(1) space." XOR everything. Then the follow-up — two numbers appear once — needs the extra step: XOR everything to get a ^ b, isolate any set bit with x & -x (a bit where a and b differ), and partition the array on that bit so each group contains exactly one of them.

"What can a Bloom filter tell you for certain?" That an item is definitely not present. A positive is only "probably". Then explain why there are no false negatives: bits are only set, never cleared.

"Your Bloom filter's false-positive rate is climbing. Why, and what do you do?" It is filling up, and there is no error — it degrades silently. You size for the expected item count up front, monitor the fill ratio, and rebuild or shard when it is exceeded. Deletion is not available, so a counting Bloom or cuckoo filter is the alternative.

"This problem is NP-hard. What do you do?" Not "give up". Name the ladder: exponential-but-smart for small n, an approximation with a proven ratio, a heuristic, exploiting the structure of your real inputs, or relaxing the optimisation into a feasibility question. The last one is the most valuable and the least often given.

"Knapsack DP is O(nW), which is polynomial. Is knapsack in P?" No — this is the pseudo-polynomial trap and it is a genuinely good question. W is a value, and writing it takes \log W bits, so O(nW) is exponential in the input's actual size. A capacity of 2^{60} makes the table impossible even though the formula looks polynomial.

One thing to volunteer: state the design test for any probabilistic structure — what does a wrong answer cost? A false positive that triggers one extra database lookup is free; a false positive that skips a payment check is a defect. That single question decides whether the structure is appropriate, and it is the one senior engineers ask first.

Recall

• x & (x-1) clears the lowest set bit (so looping it counts set bits in as many steps as there are 1s); x & -x isolates it (the Fenwick tree's engine).
• XOR cancels duplicates: a^a = 0, so XOR-ing a list leaves only the value appearing an odd number of times — O(1) space instead of a hash set.
• A bitmask is a set of up to ~30 items in one integer, which makes subset enumeration a loop and gives bitmask DP its O(2^n n^2) TSP.
• A Bloom filter can say definitely not, never definitely yes; there are no false negatives because bits are only set, never cleared. ~10 bits per item gives ~1% error, and it degrades silently as it fills. No deletion.
• Count-Min Sketch takes the minimum across rows because collisions only inflate; HyperLogLog's real value is mergeability, since exact daily uniques cannot be summed into a month.
• NP-hard means no known polynomial algorithm. The five responses: exponential-but-smart, approximation with a proven ratio, heuristics, exploiting your real inputs' structure, or relaxing the optimisation into a feasibility question.
• Knapsack's O(nW) DP is pseudo-polynomial — exponential in the number of bits of W, not polynomial in the input size.

Self-test: Why does x & (x-1) clear exactly the lowest set bit? · Extend the XOR trick to the case where two numbers appear once · Why does a Bloom filter have no false negatives? · Why can exact daily unique counts not be summed, and how does HyperLogLog fix it? · Why is O(nW) not proof that knapsack is in P?

Next: 4.30 turns the bit idioms above into the seven NeetCode problems that test them, one page per problem.