on May 28, 2005
First of all, the book itself is incredible.
The title was poorly chosen, I think. The connotation of "hacker" in the public mind is somewhat different than the word's meaning forty years ago at MIT, and I found (and continue to find) this book shelved alongside ephemera about firewalls and internet security. Thinking it was about "1337 hacking", I picked it off the shelf for a quick sneer. Six hours later, the bookstore had to kick me out because they were closing.
Think of it as "The Art of Computer Programming, Volume 0: Bit Manipulation". Except without the annoying Knuth attitude.
"Hacker's Delight" is a timeless classic, a scholarly and exhaustive treatment of finite-word-length arithmetic and other bit-manipulation algorithms. The book is excellently written and the material lovingly presented. For some people (such as me), the mathematical beauty and cleverness of the solutions is reason enough to find the book fascinating. For other people (such as me), there are extensive practical applications.
However, the size of the latter group (or, perhaps, relative percentage) is dwindling with time. A programmer who thinks that the universe begins and ends with Oracle and PHP respectively is unlikely to need an 8-RISC-instruction algorithm for dividing integers by 7. The essence of programming is abstraction, and as computational resources become more abundant, the path of progress abstracts further and further away from the machine. For many modern programmers, there are no bits -- there are only "numbers" (double-precision floats, typically), and the hardware handles these floats just as gracefully as integers. In this world, one's complementing and shifting have no meaning.
Even for those working at a lower level, the caching and pipelining schemes of modern architectures can complicate some of the assumptions in this book. For example, branch performance is highly architecture-dependent, and the efficiency that can be gained through branch tuning can outweigh that of shaving off a few instructions. Warren is careful to provide and identify branch-free algorithms whenever possible, but it often is not. As another example, parallel instruction scheduling means that not only is a routine no longer the sum of its instructions' cycles, it's not even completely deterministic, at least from the programmer's perspective.
But I work in the embedded field, and my targets have ranged from 1 MHz 8-bit 6502s through 50 MHz 32-bit Coldfires to creatively-handicapped DSPs of various sorts. Not a FPU or branch predictor in sight. In such situations, the algorithms in "Hacker's Delight" can be lifesavers. Not to mention, so much fun! If you approach optimization as a puzzle, wherein the solution is its own reward, this book is indeed a compendium of delights.
Many descriptions of this book refer to it as a collection of programming "tricks". I dislike that word; it implies a casualness and triviality that does not befit a book of this rigor and scope. I prefer the subtitle of Johnson and Graham's text on high-speed digital design: "A Handbook of Black Magic".
If your magic dust is bits and cycles, this is your spellbook.
on August 18, 2002
Early drafts of Dr Warren's book have circulated for several years samizdat style among a group of hardware, compiler and OS people at a large computer research lab. One copy in particular always sits about three feet from me. If the building were to catch on fire, you might very well hear shouts of "who's taking Hacker's Delight?"
How do you determine, using the smallest number of instructions, if a word contains at least one zero byte? How do you transpose a bit matrix? Divide by 5? Count the number of ones in a word? Permute bits? Maybe you're smart enough to already know. Or perhaps you know someone else who does. For the rest of us there's Hacker's Delight.
Some years back, in the course of building a large machine, we made a mistake that resulted in some very expensive rework. Just one particular paragraph in this book would have saved us an amount of money best not admitted in print. If you have Knuth on your shelf then there's a good chance that you'll want Hacker's Delight right next to it.
And just in case life is getting too serious, there are some entertaining chapters on prime numbers and Hilbert curves, written so compellingly that you can't stop reading until the end.
Highly recommended. If this book relates to the kind of work you do, then don't leave home without it.
on October 22, 2002
I feel compelled to point out that this book is _not_ a few things: It's not a book that teaches you how to break into computers, or crack codes. It's also not the kind of book that teaches you how to do something which you don't know how to do.
This book is a collection of tricks that show the reader better ways to do things they already know how to do. And it's also a book that can give the reader insight into different approaches and mechanisms for solving problems.
Computer programmers translate their ideas and requirements into any of several computer languages. Those expressions are limited by the language the programmer is using, and maybe even the machine the programmer is targeting. But there is a wide continum of expressions that result in the same -- hopefully correct -- results. Choosing the most efficient, and most elegant, expression to some is "real" hacking.
This book is for real hackers. It's a great collection of tricks for performing usually simple operations in an elegant way. What's elegant? Well, elegant is efficeint. If there's a side-effect of an elegant operation, it turns out that side-effect is probably useful and not simply discarded.
This book catalogs insights into concrete binary math, shortcuts derived from different boolean operators, and even approaches some interesting numerical analysis problems.
If you already know how to write software, and you already know you want to find faster or more efficient ways to check for overflows on integers, divide nubmers, count bits, search for binary patterns, or do other twiddling, then this book is for you.
If the application of such techniques doesn't seem important to you, then this book probably isn't going to be of interest to you.
on April 27, 2005
Warren was one of the editors of the PowerPC compiler guide and that book had two neat chapeters, "Clever Examples," and "Optimal Code Sequences," which introduced the use of the gnu superoptimzer. The PPC Compiler Writer's guide was useful for more than Compiler Writers! Warren's book Hacker's Delight is a greatly expanded version of that material. He introduces a basic RISC and proceeds to give C, pseudocode and basic RISC assembly for many different operations. What distinguishes Hacker's Delight is that he goes into cycle counts and optimzation strategies for some of the algorithims and analyzes tradeoffs for different solutions. Some of bits I have applied the techniques to my day job are in ch. 7: Rearranging Bits and Bytes and Chs. 5 & 6 "Counting Bits" and "Searching Words" There is some good material on computer arithmetic including using a radix -2 system, and a chapter on Hilbert's Curves as well as Primes, which I haven't gotten a chance to enjoy yet. Be sure to check his website for errata and some additional material. Highly Recommended.
on February 11, 2003
If you love the nuts and bolts of logical operations in computer programming, do I have a book for you! This book does a great job of describing in reasonable detail logical operators and what you can do with them ranging from very basic "what is it" to reasonably advanced applications such as wierd base -2 math, division, pattern matching, etc. I found this book to be a great reference and refresher clearly layed out and easy to read. I wish my software engineer co-workers would read this book. I'm tired of seeing ugly code (a while loop with a mod operator to align data pointers on, say, 8 byte boundaries).
This book is an absolute essential to the right reader. That right reader is either a low-level coder, a high-level logic designer, or someone who builds tools and libraries for same. In other words, not a lot of people. This is hacking at its bit-level finest, though. If you're among those few, or think you might be, or want a good laugh at the people who are, dig in.
It's good for things like counting the number of 1 bits in a word-length integer (hint: if you count the bits, you're doing it the hard way). It's good for things like fast division by an integer constant, or mod to a constant integer modulus (hint: if you perform division by dividing, you're barking up the wrong tree). If you can look into a 32x32 bit multiplication and see a convolution going on, you're way ahead of the game. The only tricks I know that didn't appear here are A) for purposes that almost no one has or B) for machines that almost no one has.
Warren presents the coolest collection of slimy coding tricks ever collected, with full attention to the number of machine cycles and the compiler-writer's unique needs. I've seen a lot, and this is by far the biggest and coolest collection around. I have two complaints, though, a small one and a really big one. The small one is that the author didn't score a direct bullseye on my somewhat offbeat needs. Well, he never tried to - that's just me griping that he didn't write a different book. The big complaint is that pages, lots of them, just fluttered out of this pricey book and onto the floor. GRRR. This takes nothing away from the content of the book, until some critical page flutters off never to be seen again. Still, if you can keep a rubber band around it, this will be one of the deepest mines of coolness in your uber-geek library.
Update for second edition: I rarely recommend spending money on a new edition to anyone who has the first (even if it holds its pages), but this is an exception. The second adds material on division and mod operations, for example finding remainders without division. It also mentions CRCs and error correction, adds bits and scraps to many sections, and includes solved problems. The improvement is really worth having.
The term "hacker" in this book means someone who enjoys making computers do interesting tricks regardless of whether it turns out to be useful, not someone who is intent on circumventing computer security. Plus, how relevant would those kind of tips be coming from a book that was written in 2002? Don't let the author's definition of a hacker fool you, though - the tricks in this book are very useful.
This book is a collection of small programming tricks on various subjects. The presentation is very informal, and the methods use very basic computer math. You should know your binary number system backwards and forwards before you start this book. Either C or assembly language is used to demonstrate the hacks in code form. When assembly language is used, it is that of a fictitious machine that is representative of RISC computers. That is because the tricks are meant to be platform independent.
After disposing of basic arithmetic operations early in the book, the author turns his attention to more complex math problems such as calculating square roots. His discussion of the subject is both complex and simple. First, he explains Newton's method of computing square roots through a page full of equations that require some effort to follow. Then he gives an implementation that requires fewer than twenty lines of C code. This is followed by another method that is longer and more cryptic but executes faster, by using a binary search algorithm. Whether you are interested in the equations or merely need the C code to do your job, these solutions are efficient and elegant.
Other topics addressed include Gray codes, the Hilbert curve, and prime numbers. Gray codes are a method of arranging the integers from 1 to N in a list so that each number can be visited exactly once by flipping only one bit at a time. The Hilbert curve is a similar idea expressed geometrically: a single continuous curve which, given a space divided into a grid of squares, touches every square exactly once and does not cross itself. In each case, both the mathematical discussion and the code to solve the problem are provided.
The chapter on prime numbers is the most challenging mathematically but also one of the most interesting. It starts with a concise overview of various mathematicians' efforts to devise ways of finding prime numbers. The author is one of those people who periodically become fascinated by some problem and devote themselves to learning more about it and searching for a solution. The chapter ends not with the usual code sample, but instead with an invitation to continue the search for interesting solutions to the problem.
Clearly, the author views this book not as a finished collection, but rather as a snapshot of work in progress. After decades of interest-driven research, the author has amassed a collection of studies big enough to fill a book, and it is fortunate for the rest of us that he has written one.
on January 2, 2011
Don't be fooled by the title, this is not a book about hacking in the sense of compromising a computer, but rather the original sense of the word "hacker," as in, thinking outside of the box to solve a problem. This book is a collection of various techniques that one might employ to solve certain classes of problems that arise during programming, and in rather clever ways to boot. The flexibility of programming languages underscores the old phrase "there's more than one way to skin a cat," so all things being equal the best method is usually the one that executes the fastest. How about finding the sign of a number in three instructions, and not using an if statement? How about multiplication, division, or counting the number of zero/one bits in a word? The solutions that are presented are nothing short of genius with operation counts approaching "obscenely few." Admittedly, everything comes with trade-offs: some of the solutions are so very compact that if you came across the code and it didn't have comments it wouldn't be obvious about what is going on. Thankfully, that isn't the case in the book. Warren does an admirable job of explaining not only what is going on but why, and in very casual/engaging prose.
So why should you get this book? The author even admits that any compiler worth its salt will implement most of these solutions when it starts digesting your code. However, more often than not the name of the game is "ask not what your compiler can do for you, but what you can do for your compiler." Optimizing compilers can do some pretty good stuff if you look at the assembly, but sometimes thinking creatures (humans) can do better. A lot better. This book explains some of the things that compilers will do for you. For your own sake, don't approach a compiler and linker as black boxes; learn what happens under the hood- you will be a much better programmer.
I heartily recommend this book to intermediate and advanced programmers looking for some really slick tricks to add to your "toolbox." The emphasis is far and above on integer math, so this definitely isn't the place to look for floating-point tricks. If you are still new to programming, revisit this after you've gotten your feet wet and know a little bit of binary mathematics.
on January 27, 2005
Anyone can reverse the bits in a byte, so the LSB is in the MSB position etc., using a while loop. Only thing is, there's a quicker way using multiplication, and that way is in this book. Lots of embedded and kernel developers twiddle bits for a living. This book describes so many techniques that I've used or needed. I wish I'd been handed this book at the beginning of my career instead of in the middle. You won't use this book every day, but every day you use it will save you a week, or more importantly a few desparately needed microseconds. It's intensely practical, not theoretical. It can be a little hard to find what you're looking for here, but mostly because it's so densely packed. It's way too nerdy for the merely curious, but quite the indispensible reference for the seasoned bit-pusher.
on February 25, 2005
I would rate this book up there as to eventually be one of the CS classics. I can't imagine anything pertaining to binary arithmetic that's not covered! OK, so that's a slight embellishment, but still this book has just about everything you could want to know about bit manipulation at the lowest levels. Powers of 2, arithmetic bounds, counting words, searching words, rearranging bits and bytes, squares, cubes, signed and unsigned division oh my! This book contains one of the better explanations on floating numbers as well. This book was well worth the price I paid and if you smack of geek to the core, I think you'll find the same to be true for you. I only wish I had read this book prior to some hard core job interviews of yore :-)