Author: Donald E. Knuth Publisher: AddisonWesley Professional Pages: 272 ISBN: 9780321580504 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 preprints 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 nbit 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.
