Henry S. Warren Jr. - Hackers Delight

When I first got a summer job at MIT'sProject MAC almost 30 years ago, I was delighted to be able to work with theDEC PDP-10 computer, which was more fun to program in assembly language thanany other computer, bar none, because of its rich yet tractable set ofinstructions for performing bit tests, bit masking, field manipulation, andoperations on integers. Though the PDP-10 has not been manufactured for quitesome years, there remains a thriving cult of enthusiasts who keep old PDP-10hardware running and who run old PDP-10 softwareentire operating systems andtheir applicationsby using personal computers to simulate the PDP-10instruction set. They even write new software; there is now at least one Website whose pages are served up by a simulated PDP-10. (Come on, stoplaughingit's no sillier than keeping antique cars running.)

I also enjoyed, in that summer of 1972,reading a brand-new MIT research memo called HAKMEM, a bizarre and eclecticpotpourri of technical trivia. [1] Thesubject matter ranged from electrical circuits to number theory, but whatintrigued me most was its small catalog of ingenious little programming tricks.Each such gem would typically describe some plausible yet unusual operation onintegers or bit strings (such as counting the 1-bits in a word) that couldeasily be programmed using either a longish fixed sequence of machineinstructions or a loop, and then show how the same thing might be done muchmore cleverly, using just four or three or two carefully chosen instructionswhose interactions are not at all obvious until explained or fathomed. For me,devouring these little programming nuggets was like eating peanuts, or ratherbonbonsI just couldn't stopand there was a certain richness to them, a certainintellectual depth, elegance, even poetry.

[1] Why "HAKMEM"? Short for "hacks memo"; one36-bit PDP-10 word could hold six 6-bit characters, so a lot of the namesPDP-10 hackers worked with were limited to six characters. We were used toglancing at a six-character abbreviated name and instantly decoding thecontractions. So naming the memo "HAKMEM" made sense at the timeatleast to the hackers.

"Surely," I thought, "theremust be more of these," and indeed over the years I collected, and in somecases discovered, a few more. "There ought to be a book of them."

I was genuinely thrilled when I saw HankWarren's manuscript. He has systematically collected these little programmingtricks, organized them thematically, and explained them clearly. While some ofthem may be described in terms of machine instructions, this is not a book onlyfor assembly language programmers. The subject matter is basic structuralrelationships among integers and bit strings in a computer and efficienttechniques for performing useful operations on them.

These techniques are just as useful in the Cor Java programming languages as they are in assembly language.

Many books on algorithms and data structuresteach complicated techniques for sorting and searching, for maintaining hashtables and binary trees, for dealing with records and pointers. They overlookwhat can be done with very tiny pieces of databits and arrays of bits. It isamazing what can be done with just binary addition and subtraction and maybesome bitwise operations; the fact that the carry chain allows a single bit toaffect all the bits to its left makes addition a peculiarly powerful datamanipulation operation in ways that are not widely appreciated.

Yes, there ought to be a book about thesetechniques. Now it is in your hands, and it's terrific. If you write optimizingcompilers or high-performance code, you must read this book. You otherwisemight not use this bag of tricks every single daybut if you find yourself stuckin some situation where you apparently need to loop over the bits in a word, orto perform some operation on integers and it just seems harder to code than itought, or you really need the inner loop of some integer or bit-fiddlycomputation to run twice as fast, then this is the place to look. Or maybeyou'll just find yourself reading it straight through out of sheer pleasure.

Guy L. Steele, Jr.
Burlington, Massachusetts
April 2002