Author: Donald E. Knuth
Publisher: Addison-Wesley Professional
Pages: 272
ISBN: 978-0321580504
Aimed at: Academic and practicing programmers
Rating: 5
Pros: Deep coverage of core topics that is fun to read
Cons: A very short volume
Reviewed by: Mike James

If you are waiting for the later volumes in Donald Knuth's The Art of Computer Programming then the slim "fascicles" are all you can get at the moment. These are essentially pre-prints of bits of the work that Knuth has finished. Think of them as proof that the project is still on going.

This Fascicle is from Volume 4 (even though it has a huge figure one on the cover indicating it is Fascicle 1) and its subtitle tells you what it's all about - bitwise techniques and binary decision diagrams. This sounds like very simple stuff and you might be tempted to believe that you knew everything there was to know about both subjects. After all bit "fiddling" is core to any reasonable programmer's education and we all love to collect strange tricks and techniques as we go along.

Don't be fooled you will find much that you had no idea existed in the first part of this book. It is written in Kunth's fairly academic style but even skim reading should get you interested. Topics covered include basic things like accessing particular bits using logical operations, bit reversal, permutation and so on… and even though you might think you know all about these techniques Knuth manages to find something new in each.

Then he moves on to his central idea - broadword computing - i.e. the idea of creating algorithms which are parallel at the bit level. As he puts it,

"Broadword computing is the art of dealing with n-bit words where n is a parameter that is not extremely small."

The examples given include processing bitmaps, data structures and branchless computation.

Similarly the second half of the book also deals with what is on the face of it a simple idea - binary decision diagrams BDDs. Essentially a BDD is the map of set of binary decisions that implement a truth table. The input variables take you down a particular path through the diagram with the result that a one or a zero is output. Very simple but as you might be coming to expect from anything Knuth tackles there is so much more to it.

BDDs deserve to be better known as it is clear they and the bitwise operations introduced in part one have practical applications. It is worth noting that there isn't very much to this already thin book when you take away the exercises and the solutions to the exercises - about 70 pages. All worth tackling, however, and if you like puzzles of any sort the book is also great fun to read.