Advanced Techniques

Bit Manipulation

An integer stores its value in binary. Treating those bits as separate flags is the basis of bitmasks (the DP over subsets in Dynamic Programming used one), bitsets, hashing, and compact protocols. The demo is 69_bit_manipulation.go.

The Operators

Go defines shifts fully: shifting by the width of the type or more gives 0 for unsigned values (the demo prints 1<<64 = 0 for a variable shift count), and there is no undefined behavior as in C. Shifting a signed negative number right keeps the sign. Use unsigned types for bit patterns.

The Two Identities

Subtracting 1 from a number flips its lowest 1 bit to 0 and every 0 below it to 1. That single fact gives two identities that solve many problems:

x & (x-1) clears the lowest set bit; x & -x isolates it.

func popcount(x uint) int {
	n := 0
	for ; x != 0; x &= x - 1 {
		n++
	}
	return n
}

func isPowerOfTwo(x uint) bool { return x != 0 && x&(x-1) == 0 }

popcount counts the set bits by clearing one per iteration: as many steps as there are ones, not as many as there are positions. A power of two has exactly one set bit, so clearing it leaves zero. In real code use bits.OnesCount from math/bits, which compiles to a single instruction; the demo checks the loop, a 64-step loop and the library function against each other on 20,000 values. Failures: 0.

Enumerating Submasks

To visit every subset of the bits of a mask (including the mask itself and 0), start at the mask and repeatedly compute (sub - 1) & mask. Subtracting 1 drops to the next lower number; AND-ing with the mask throws away the bits that are not allowed. The numbers come out in decreasing order and none is skipped:

func forEachSubmask(mask uint, visit func(sub uint)) {
	for sub := mask; ; sub = (sub - 1) & mask {
		visit(sub)
		if sub == 0 {
			return
		}
	}
}

For 101101 the demo prints 16 submasks, 2⁴ because the mask has four set bits, from 101101 down to 000000. It matches "filter every number up to the mask" on 300 random masks. This loop is the engine of DP over subsets, where a state is a set and its transitions look at its subsets.

Gray Codes and Gosper's Hack

A Gray code lists the numbers so that neighbours differ in exactly one bit, useful for encoders and for changing one setting at a time. The n-th code is n ^ (n >> 1): for 0 to 7 it is 000 001 011 010 110 111 101 100. The demo verifies the one-bit property for all 65,536 codes of 16 bits.

Gosper's hack produces the next larger number with the same number of set bits, which enumerates all k-element subsets of n items in increasing order without recursion:

func nextSamePopcount(x uint) uint {
	c := x & -x // lowest set bit
	r := x + c  // carries through the lowest block of ones
	return (r^x)>>2/c | r
}

Adding the lowest bit makes the lowest block of ones carry into the next zero; the leftover ones are shifted back to the bottom. The demo checks that starting from (1<<k)-1 it visits exactly the numbers below 2ⁿ with k set bits, in order, for every n up to 12 and every k. Failures: 0.

XOR Puzzles

XOR has three properties: a ^ a = 0, a ^ 0 = a, and the order does not matter. XOR-ing a whole array therefore cancels every value that appears twice, and what is left is the value that appears once:

func singleNumber(nums []int) int {
	x := 0
	for _, v := range nums {
		x ^= v
	}
	return x
}

With two values appearing once (call them a and b), the XOR of everything is a ^ b, which is not zero. Any set bit in it is a position where a and b differ, so splitting the numbers by that bit puts a and b in different groups, and each group is the previous problem. The demo plants two singles among random pairs and shuffles: 2,000 arrays, failures: 0. A related trick finds the missing number in 0..n by XOR-ing all the indexes with all the values, in O(n) time and O(1) space.

A well-known puzzle swaps two integers with three XORs and no temporary. It is also a trap: if both pointers refer to the same variable, the first line zeroes it, and the demo shows swapXor(&same, &same) turning 7 into 0. A temporary variable is clearer and never slower.

A Bitset

A []bool uses one byte per flag. A bitset packs 64 flags into each uint64: eight times less memory, and set operations that handle 64 elements per instruction.

func (b Bitset) Set(i int)       { b[i>>6] |= 1 << (i & 63) } // i>>6 = i/64, i&63 = i%64
func (b Bitset) Clear(i int)     { b[i>>6] &^= 1 << (i & 63) }
func (b Bitset) Test(i int) bool { return b[i>>6]>>(i&63)&1 == 1 }

Bit i lives in word i/64 at position i%64; shifting and masking is faster than division. Union is OR, intersection is AND, difference is AND NOT, and counting is bits.OnesCount64 per word:

func (b Bitset) Intersect(o Bitset) {
	for i := range b {
		b[i] &= o[i]
	}
}

The demo sieves the primes below 5,000,000 both ways. Both find 348,513 primes; the bitset uses 625,000 bytes and the []bool 5,000,000. Intersecting the multiples of 2 and 3 below 1,000 takes 16 word operations and leaves the 167 multiples of 6.

Randomized Algorithms

Randomness is a design tool, not only a source of test data. Two families are worth knowing by name:

• Las Vegas algorithms are always correct; only the running time is random. Randomized quickselect is expected O(n) on every input.
• Monte Carlo algorithms are always fast; the answer is correct with high probability. Miller-Rabin primality and Freivalds' matrix check are examples.

Two ideas make this practical. A fixed rule can be defeated by a bad input, but no input can defeat a random choice, because the adversary cannot predict it. And a Monte Carlo error of 1/2 per trial falls to 2^-20 after 20 independent trials: repetition turns a weak guarantee into a strong one. The demo is 70_randomized.go. Results that are random are tested statistically, with fixed seeds so the output is identical on every run.

Shuffling: The Tempting Bug

To shuffle a slice, swap every position with a random position of the whole slice. It looks fair, and it is not:

	for i := range a {
		j := rng.Intn(len(a))
		a[i], a[j] = a[j], a[i]
	}

This makes nⁿ equally likely sequences of choices, and n! does not divide nⁿ, so some permutations must be more likely than others. Fisher-Yates chooses, for position i, only among the positions that are still undecided. That gives n × (n−1) × ... × 1 = n! paths, one for each permutation:

	for i := 0; i < len(a)-1; i++ {
		j := i + rng.Intn(len(a)-i)
		a[i], a[j] = a[j], a[i]
	}

The demo shuffles [1 2 3] 600,000 times each way; a fair shuffle gives each of the six permutations 100,000 times:

A chi-square statistic summarizes how far a table is from uniform. For six outcomes anything above 20.5 is suspicious at the 0.1% level: the biased shuffle scores 7,212 and Fisher-Yates 8.0. Real code should call rand.Shuffle, which is Fisher-Yates.

Reservoir Sampling

Pick k items uniformly from a stream whose length you do not know and cannot store, such as log lines or a file read once. Keep the first k. Then, for item number i (counting from 1), replace a random slot with probability k/i:

	for i, v := range stream {
		if i < k {
			sample = append(sample, v)
		} else if j := rng.Intn(i + 1); j < k { // probability k/(i+1)
			sample[j] = v
		}
	}

Why is this fair? Item i is kept when it arrives with probability k/i, and then it survives each later step j with probability 1 − 1/j. The product telescopes: k/i × i/(i+1) × ... × (n−1)/n = k/n, the same for every item, whatever n turns out to be. The demo samples 3 of 10 items 200,000 times: every item should be chosen 60,000 times, and the counts range from 59,763 to 60,216, a 0.8% spread. Memory is O(k), independent of the stream.

Quickselect

The k-th smallest element does not need a full sort. Partition around a pivot, then keep only the side that contains index k, as in quicksort but with a single recursive call. The partition here is three-way (smaller, equal, larger), so inputs with many duplicates do not degrade:

		lt, i, gt := lo, lo, hi // invariant: [lo,lt) < pv, [lt,i) == pv, (gt,hi] > pv
		for i <= gt {
			*cmps++
			switch {
			case a[i] < pv:
				a[lt], a[i] = a[i], a[lt]
				lt++
				i++
			case a[i] > pv:
				a[i], a[gt] = a[gt], a[i]
				gt--
			default:
				i++
			}
		}
		switch {
		case k < lt:
			hi = lt - 1
		case k > gt:
			lo = gt + 1
		default:
			return pv
		}

With a random pivot, each round is expected to remove a constant fraction of the elements, so the total work is about 3 to 4 comparisons per element: O(n) expected for every input. With "the first element" as the pivot, an already sorted array removes one element per round. The demo finds the median of 20,000 numbers:

The fixed rule is fine on shuffled data and 32 times worse on sorted data; the random pivot is equally good on both. Both versions match sorting on 3,000 arrays with many duplicates. Failures: 0. (Go's slices.Sort uses pattern-defeating quicksort for the same reason: no single input should be bad for it.)

Miller-Rabin Primality

Trial division needs up to √n steps, hopeless for a 64-bit number. The Fermat test is based on the fact that for a prime n, an−1 ≡ 1 (mod n). It is fooled by Carmichael numbers such as 561 = 3 × 11 × 17, which pass for every base coprime to them: the demo shows fermat(561, 2) returning true.

Miller-Rabin strengthens it. Write n − 1 = d × 2^r with d odd. If n is prime, then for any base a either a^d ≡ 1, or squaring a^d up to r − 1 times reaches −1 (mod n), because the only square roots of 1 modulo a prime are 1 and −1. If neither happens, a is a witness that n is composite:

	d, r := n-1, 0
	for d%2 == 0 {
		d /= 2
		r++
	}
	for _, a := range testBases {
		x := powMod(a, d, n)
		if x == 1 || x == n-1 {
			continue
		}
		witness := true // a proves n composite unless -1 shows up
		for i := 1; i < r; i++ {
			x = mulMod(x, x, n)
			if x == n-1 {
				witness = false
				break
			}
		}
		if witness {
			return false
		}
	}
	return true

A composite number fools at most a quarter of the bases, so with random bases this is a Monte Carlo test. Using the twelve smallest primes as bases is proven to be exact for every n below 3.3 × 10²⁴, which includes all 64-bit numbers, so isPrime here is deterministic. The products need 128 bits; bits.Mul64 and bits.Div64 compute a*b mod m without overflow:

func mulMod(a, b, m uint64) uint64 {
	hi, lo := bits.Mul64(a, b)
	_, rem := bits.Div64(hi, lo, m) // requires hi < m, true because a, b < m
	return rem
}

The demo compares isPrime with a sieve for every number below 2,000,000 (failures: 0), and tests hard cases: 561 is rejected; 3,215,031,751, a composite that passes the tests for bases 2, 3, 5 and 7, is rejected; the Mersenne prime 2⁶¹−1 and 18,446,744,073,709,551,557, the largest prime below 2⁶⁴, are accepted; the product of 1,000,000,007 and 998,244,353 is rejected.

Freivalds: Checking a Product

Is A × B = C for three n × n matrices? Multiplying costs O(n³). Freivalds' check picks a random 0/1 vector r and compares A(Br) with Cr. Each side is two matrix-vector products, O(n²):

		if !slices.Equal(mulVec(a, mulVec(b, r)), mulVec(c, r)) {
			return false // certainly wrong
		}

If A × B = C the two sides always agree. If not, they differ for at least half of the possible vectors r, so one round misses the error with probability at most 1/2. The demo takes a correct 60 × 60 product, changes one entry among 3,600, and runs the check 4,000 times for each number of rounds:

A correct product is always accepted. The same pattern, "verify cheaply with a random probe", is used to check big computations, polynomial identities, and file transfers.

Approximate Answers in Fixed Memory

An exact set or map needs memory proportional to the number of items. When the data is huge (billions of URLs, a day of network traffic), an approximate answer with a known error can be worth far more than an exact one that does not fit. The structures below hash each item to several positions in a fixed-size array. The demo is 71_bloom_and_sketches.go. Both share a helper that derives two 64-bit hashes from a key; position i of a structure then uses h1 + i*h2, so k positions cost two hash computations instead of k ("double hashing").

Bloom Filter: Have I Seen It?

A Bloom filter is an array of m bits. To add a key, set k bits chosen by k hash positions. To look up a key, check the same k bits: if any is 0, the key was certainly never added; if all are 1, it may have been, because other keys could have set those bits. It has no false negatives, only false positives, and it cannot delete.

Two keys in a 16-bit filter. A 0 bit is proof of absence; all 1s is only a "maybe".

func (b *Bloom) Add(key string) {
	h1, h2 := hash2(key)
	for i := 0; i < b.k; i++ {
		pos := (h1 + uint64(i)*h2) % b.m
		b.words[pos/64] |= 1 << (pos % 64)
	}
}

	for i := 0; i < b.k; i++ {
		pos := (h1 + uint64(i)*h2) % b.m
		if b.words[pos/64]>>(pos%64)&1 == 0 {
			return false
		}
	}
	return true

Sizing. For n keys and a target false-positive rate p, the best number of bits and hash positions are:

	m := uint64(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
	k := int(math.Round(float64(m) / float64(n) * math.Ln2))

That is about 9.6 bits per key and 7 hashes for p = 1%, and 14.4 bits for p = 0.1%, whatever the length of the keys. The demo builds a filter for 100,000 keys: 958,506 bits (117 KB). All 100,000 added keys are found (no false negatives), and of 100,000 keys that were never added 980 are reported present: 0.98%, against the 1.00% predicted by the formula (1 − e−kn/m)k.

More memory buys a lower error, and the measured rates follow the theory closely:

Two filters of the same size and hash count merge with a bitwise OR, which contains the keys of both (the demo checks that none is lost). Typical use: put a Bloom filter in front of a slow lookup, a disk table or a remote cache. A "certainly absent" answer skips the lookup entirely; a "maybe" costs the lookup you would have done anyway, so only the 1% of false positives are wasted. Databases such as those built on LSM trees use exactly this to avoid reading files that cannot contain a key.

Count-Min Sketch: How Often?

A Count-Min sketch answers "how many times did this key occur?" for a stream. It has d rows of w counters. Adding a key increments one counter in every row (chosen by that row's hash), and the estimate is the smallest of the key's d counters. A collision can only add to a counter, so every counter is at least the true count, and so is the minimum; taking the minimum picks the least polluted one.

The estimate is the minimum of the key's counters; it can be too high, never too low.

func (c *CountMin) Add(key string, count uint32) {
	h1, h2 := hash2(key)
	for i := range c.rows {
		c.rows[i][(h1+uint64(i)*h2)%c.width] += count
	}
}

func (c *CountMin) Estimate(key string) uint32 {
	h1, h2 := hash2(key)
	best := uint32(math.MaxUint32)
	for i := range c.rows {
		best = min(best, c.rows[i][(h1+uint64(i)*h2)%c.width])
	}
	return best
}

The size follows from two numbers you choose: the estimate is at most ε × N too high (N is the total of all counts) with probability at least 1 − δ.

	w := uint64(math.Ceil(math.E / eps))
	d := int(math.Ceil(math.Log(1 / delta)))

With ε = 0.001 and δ = 0.01 that is 5 rows of 2,719 counters: 53 KB. The demo feeds it 1,000,000 events from a Zipf distribution (a few keys very frequent, most rare, like words or URLs) with 34,110 distinct keys. No estimate is below the true count. Every estimate is within ε × N = 1,000 of the truth (the guarantee only promises 99%); the worst error is 235. The frequent keys, the ones you usually care about, are estimated almost exactly:

The error is the same absolute amount for every key, so it matters for rare keys (an estimate of 235 for a key seen twice) and hardly at all for heavy hitters. That is why Count-Min is used to find the frequent items.

HyperLogLog: Counting Distinct Items

How many different visitors are in a stream? Exactly, you need a set with every item. HyperLogLog estimates it with a fixed array of small registers. The demo is 72_hyperloglog.go.

The Coin-Flip Idea

Hash each item to a random 64-bit number. A hash that begins with j zeros appears for about one item in 2^j. So if the longest run of leading zeros ever seen is L, about 2^L different items have probably been hashed. Repeats do not matter: the same item always produces the same hash. The catch is variance: one lucky hash ruins the estimate. On 20,000 distinct items and 40 different hash seeds, this single-register estimate ranges from 8,192 to 2,097,152, with a median of 32,768.

HyperLogLog splits the hash. The first p bits choose one of m = 2^p registers; the remaining bits give the leading-zero count. Each register keeps only the maximum it has seen, and a harmonic mean over the registers gives the estimate, which damps the effect of a few lucky ones.

The first bits choose a register; the zero run updates it, keeping the maximum.

func (h *HLL) Add(key string) {
	x := hash64(key)
	idx := x >> (64 - h.p)
	rest := x<<h.p | 1<<(h.p-1)
	h.regs[idx] = max(h.regs[idx], rank(rest))
}

The rank of the remaining bits is the number of leading zeros plus one, computed by bits.LeadingZeros64. The extra 1 bit at the bottom of rest keeps the rank finite if all the remaining bits are zero. The hash must look random in every bit, so the demo passes FNV through a finalizer that spreads each input bit over all output bits.

func rank(x uint64) uint8 { return uint8(bits.LeadingZeros64(x)) + 1 }

The Estimate and Small Counts

	est := alpha * m * m / sum
	if est <= 2.5*m && zeros > 0 {
		return m * math.Log(m/float64(zeros))
	}
	return est

Here sum is the total of 2^−register and alpha is a constant near 0.72 that corrects a bias. When many registers are still 0, the count is small and the formula is inaccurate; the fallback is linear counting, which reads the array like a Bloom filter backwards: how many of the m buckets are still empty? With 16,384 registers (16 KB) the relative standard error is 1.04/√m = 0.81%, and the demo's estimates are:

The memory is 16 KB for a million items, and it would be the same for a billion. After 3,000,000 more insertions of the same keys the estimate is exactly unchanged, because a repeat can only write a value a register already holds.

Memory Against Accuracy

Each doubling of the registers cuts the error by a factor of √2. The demo builds 12 sketches of 100,000 items for each size and reports the mean absolute error. (For a normal distribution the mean absolute error is about 0.8 of the standard deviation, which is what the measured column shows.)

Merging: Unions for Free

Because a register keeps a maximum, two sketches built with the same parameters merge by taking the larger value in each register. The result is exactly the sketch of the union of the two sets, so counts computed on different servers or different days can be combined:

func (h *HLL) Merge(o *HLL) {
	for i := range h.regs {
		h.regs[i] = max(h.regs[i], o.regs[i])
	}
}

In the demo, set A holds ids 0 to 599,999 (estimate 600,519) and set B ids 400,000 to 999,999 (estimate 597,380). The merged sketch estimates 998,802 for a true union of 1,000,000, an error of 0.12%. Inclusion-exclusion gives the overlap as |A| + |B| − |A ∪ B| ≈ 199,098 (true value 200,000), but subtracting large estimates amplifies their errors, so small overlaps cannot be measured this way.

Choosing a Technique

By Situation

Exact First

Approximate structures trade accuracy for memory, so use them only when memory is the real constraint. A map[string]struct{} for a million keys is a few tens of megabytes and gives exact answers: often perfectly fine. Start with the exact version, measure, and switch when the data outgrows the machine. Keep the exact version as the oracle in your tests, as the demos do.

Common Pitfalls

Signed Shifts and Overflow

Use unsigned integers for bit patterns. A right shift of a negative signed value fills with the sign bit, and shifting 1 left by 63 places in an int variable gives a negative number. Also mind operator precedence: in Go, & and << bind tighter than + and ==, unlike in C, but parentheses cost nothing when the meaning is not obvious.

Which Random Generator?

math/rand is fast and, with a fixed seed, reproducible, which is what algorithms and tests want. It is not suitable for secrets: tokens, keys and passwords need crypto/rand. Do not reuse one seed everywhere, and do not create a new generator inside a hot loop.

Modulo Bias and Off-by-One in Random Ranges

Use rng.Intn(n), not rng.Int() % n, which is slightly biased when n does not divide the range. In Fisher-Yates and reservoir sampling the range of the random index is exactly what makes the result fair: Intn(len(a)-i) and Intn(i+1). Changing either bound silently changes the distribution, and only a statistical test will notice.

Weak Hash Functions

Bloom filters, Count-Min and HyperLogLog assume the hash bits look random. A poor hash, such as one that keeps similar keys close together, breaks the error formulas without any visible failure. Use a good 64-bit hash, or finalize a simple one as the demos do. If the input can be chosen by an attacker, seed the hash randomly at startup.

Wrong Sizing

A Bloom filter sized for n keys degrades quickly once you add many more than n: the false-positive rate is a function of the load. Size for the largest count you expect, or use a scalable variant. Two sketches can only be merged if they use the same size and hash functions.

Believing an Estimate Is Exact

A "maybe" from a Bloom filter needs the real lookup behind it. A HyperLogLog count is not a number to compare for equality, and a Count-Min estimate is an upper bound. State the error next to any figure you report.

Practice Lab

Each exercise breaks one detail. Predict what will fail, run the demo, and explain why that check catches it.

Run the Demos

1. In 69_bit_manipulation.go, change sub = (sub - 1) & mask in forEachSubmask to sub = sub - 1. What does the loop visit now, and how many of the 300 random masks fail?
2. In 70_randomized.go, change j := i + rng.Intn(len(a)-i) in shuffleFisherYates to j := rng.Intn(len(a)). Compare the two chi-square values. Then change testBases to {2}: how many numbers below 2,000,000 are misjudged, and which of the hard cases is now accepted?
3. In 71_bloom_and_sketches.go, in MayContain change uint64(i) to uint64(i+1). Bloom filters promise no false negatives; what is the count of "added keys reported absent"? Then restore it and make Estimate return the last row's counter instead of the minimum: which guarantee is lost?
4. In 72_hyperloglog.go, change max to min in Merge. What does the merged sketch estimate for the union of 1,000,000 ids, and why?

Exercises

1. Missing number. An array holds the numbers 0 to n except one. Find it with XOR in O(n) time and O(1) space, then with the sum formula, and explain when the sum could overflow.
2. Subset sums with masks. For up to 20 numbers, compute the sum of every subset by iterating over all masks, using the lowest-bit identity to reuse the sum of mask & (mask-1). Compare with the recursive version from Backtracking.
3. Weighted sampling. Sample one item with probability proportional to its weight from a stream. Adapt reservoir sampling and check the frequencies with a chi-square test.
4. Counting Bloom filter. Replace each bit by a small counter so that keys can be deleted. What can go wrong when a counter overflows, and what happens if you delete a key that was never added?
5. Heavy hitters. Keep a Count-Min sketch and a small heap of the current top 10 keys, updating the heap when an estimate rises above its smallest entry. Compare the final list with the exact top 10 on the Zipf stream.
6. HyperLogLog plus. Count the distinct values of a stream in a sliding window of the last hour by keeping one sketch per minute and merging the last 60. What error do you expect for a window of 60 sketches?

Continue with Production Structures.