Bits and maths

What do the bits know that the numbers hide?

About 70 minutes · open lesson · Coding

Eighty million ids, one without its pair

Every night a ledger is matched against the bank's settlement file. Each transaction id should appear twice, once from each side. Tonight the two sides differ by one transaction, and 80 million ids have to stream through to find it.

The obvious script adds each id to a hash set, removes it when its second copy arrives, and prints whatever is left. The reconciliation box is an old VM with 512 MB of memory, and a Python set spends around 80 bytes on every id it holds. Work it out: at 80 bytes an id, the set passes 512 MB about six million ids in, long before most pairs have closed, and the script is killed. Sorting needs the whole file in memory too.

Write down what you know. Every id but one appears twice. The order is random. Each id streams past once and cannot be read again. The box can keep almost nothing. So the answer has to be held in one number, updated as each id goes by, and that number must lose all trace of a pair as soon as both copies have passed.

Pause and predict Every id appears twice except one. Which single 64-bit number can you keep as the ids stream past?

Change the numbers, keep one quantity fixed

Some easy problems become puzzles when a tool is taken away. Find the one value without a pair, but with no hash set, as in the opening. Add two numbers, but with no +. Raise x to the power two billion, but faster than two billion steps.

In each case the way forward is to look at the bits inside the number. An int is 32 separate bit positions, which this unit calls columns, and the bit operators work on all 32 at once, in one step.

Every trick in this unit has the same shape. A loop rewrites the numbers, but one quantity stays fixed. When the loop ends, that quantity is the answer.

The invariant. Each loop keeps one quantity equal to the answer while the bits change: the XOR of the values seen an odd number of times (folding, which means XOR-ing every value into one running result), the total a + b (adding with carries), and result × base^e (fast exponentiation).

Folding. XOR is addition without carries, one column at a time, so a bit of the result is the count of 1s in that column, mod 2. Two copies of a value add an even count to each of its columns. So the running XOR depends only on which values have been seen an odd number of times. When every other value comes in pairs, only the single value has been seen an odd number of times, so the running XOR equals it.

Adding. In each column, the sum digit is a ^ b and a carry appears where a & b is 1, one column to the left. So a + b = (a ^ b) + ((a & b) << 1). Replacing a and b by the two numbers on the right keeps the same total. The carry is a multiple of 2 after one round, of 4 after two, and so on, so in 32 bits it becomes 0 within 32 rounds. At that point the total is a alone.

Powering. Start with result = 1, base = x, e = n: result × base^e is x^n. If e is odd, multiply result by base and lower e by one, which keeps the product the same. Then square base and halve e, which leaves base^e unchanged. When e reaches 0, result is x^n, and that took one round per bit of n.

Six tools, one at a time

Pause and predict 44 is 101100 in binary. What is 44 & 43?

The last two are about whole numbers and use no bits. The sieve answers "which numbers below n are prime" for all of them at once. In Euclid's algorithm the invariant is the set of common divisors of the pair, which stays the same while the numbers shrink.

Many facts in one number

Shifts and masks also pack several fields into one integer. A Snowflake-style id puts a 41-bit timestamp, a 10-bit machine id and a 12-bit sequence into one 64-bit number: (time << 22) | (machine << 12) | seq. The time sits in the top bits, so sorting the ids sorts them by when they were made, and because each machine has its own id, no two machines ever need to coordinate to pick the next one.

System design: generating unique ids

How to recognise it

The strongest signal is a missing tool: the problem demands O(1) space where a set would be natural, forbids +, or gives an exponent too large to loop over. The second signal is the phrase "modulo 10⁹ + 7", which means the true answer is huge and you should do the multiplications in long.

Pause and predict You must find the one repeated value in an array, and there is no limit on memory. Should you use XOR or a hash set?

Problems that only look like it

When you need a missing or duplicated value with no space limit, a set is simpler and fast enough. When the values fit the range of the indices, the array itself can serve as the set, as in First Missing Positive in hashing.
When bits stand for a set of chosen items, as in "list every subset", the bitmask is only a way to count through the choices. That is backtracking, or a bitmask state in bitmask DP.
When the question asks for "the smallest x such that something holds", even when x is a power, it is a search over possible answers, in binary search.

Where it bites

Pause and predict Java: what is Math.abs(Integer.MIN_VALUE)?

Negating Integer.MIN_VALUE. -(-2147483648) is -2147483648 again, and so is Math.abs of it. Widen to long before you negate.
Multiplying in int before taking the modulus. Two values below 10⁹ + 7 multiply to about 10¹⁸. Keep them in long and reduce after every product.
Using XOR when values appear three times. Three copies XOR to one copy. Count the 1s in each column mod 3 instead.
Starting the XOR at 0 in Missing Number. There are n + 1 possible values but only n indices, so start the XOR at n to include the last value.
Python and negative numbers in bit tricks. Python ints have no fixed width, so a negative number behaves as if it had infinitely many leading 1s. Mask with 0xFFFFFFFF, then turn bit 31 back into a sign at the end.

Open the interactive lesson

The interactive lesson adds the predictions with their answers, the labs, and graded practice with spaced review.