TAOCP Vol 4A: Combinatorial Algorithms, Part 1 · Week 106
TAOCP 7.1.3 Bitwise Tricks and Techniques (part 2): reading guide
Part 2 covers the more advanced half: broadword computing (treating a 64-bit word as a small parallel computer), bit permutations and transposes, working with bitmaps and graphics rasters, and related applications.
Time About 8 hours this week
Why it matters
Broadword (SWAR) techniques are the basis of fast string search, SIMD-style parsing and succinct data structures.
Before you start
- 7.1.3 part 1
How to approach it
Implement a SWAR trick to find a zero byte in a 64-bit word (the trick used in fast strlen). Pick one or two larger applications from the section and code them.
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
- Endianness assumptions when packing bytes into words.