TAOCP 7.1.3 Bitwise Tricks and Techniques (part 1): reading guide

Part 1 covers the basics of bitwise operations as a tool: bit sets, extracting and isolating the rightmost bits, the ruler function, counting bits (sideways addition), and working with packed bit fields.

Time About 8 hours this week

Why it matters

This is the most directly useful part of Vol 4 for systems programmers: bitboards, compact sets, hashing, compression and fast parsers all rely on these tricks.

Before you start

7.1.1 Boolean Basics
Two's complement

How to approach it

Keep a file of tricks and test every one in C with 64-bit integers. Compare with what your compiler emits for popcount and count-trailing-zeros. Vol 4 uses MMIX (Knuth's 64-bit RISC machine) instead of MIX where it shows machine code, and much of it is written in plain algorithm steps. You will want MMIX basics (from Vol 1 Fascicle 1 or the MMIX page) for 7.1.3 especially.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Undefined behavior in C when shifting by 64 or shifting signed negative values.