Week 105 of 125
TAOCP 7.1.3 Bitwise Tricks and Techniques (part 1)
Sign up or sign in to tick these off and give this week a due date.
-
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.