Hacker's Delight

by Henry S. Warren Jr.

"This is the first book that promises to tell the deep, dark secrets of computer arithmetic, and it delivers in spades. It contains every trick I knew plus many, many more. A godsend for library developers, compiler writers, and lovers of elegant hacks, it deserves a spot on your shelf right next to Knuth."

—Josh Bloch

"When I first saw the title, I figured that the book must be either a cookbook for breaking into computers (unlikely) or some sort of compendium of little programming tricks. It's the latter, but it's thorough, almost encyclopedic, in its coverage."

—Guy Steele

These are the timesaving techniques relished by computer hackers—those devoted and persistent code developers who seek elegant and efficient ways to build better software. The truth is that much of the computer programmer's job involves a healthy mix of arithmetic and logic. In Hacker's Delight, veteran programmer Hank Warren shares the tricks he has collected from his considerable experience in the worlds of application and system programming. Most of these techniques are eminently practical, but a few are included just because they are interesting and unexpected. The resulting work is an irresistible collection that will help even the most seasoned programmers better their craft.

Topics covered include:

A broad collection of useful programming tricks Small algorithms for common tasks Power-of-2 boundaries and bounds checking Rearranging bits and bytes Integer division and division by constants Some elementary functions on integers Gray code Hilbert's space-filling curve And even formulas for prime numbers!

This book is for anyone who wants to create efficient code. Hacker's Delight will help you learn to program at a higher level—well beyond what is generally taught in schools and training courses—and will advance you substantially further than is possible through ordinary self-study alone.

Genres: Programming, Computer Science, Technology, Nonfiction, Computers, Technical, Software

Paperback

First published July 27, 2002

Reviews

[Ushan · Rating 2 out of 5]

Imagine a minicomputer programmer in 1972 or a microcomputer programmer in 1982 who needed to implement more integer operations than the standard plus, minus, bitwise and, or and xor provided by the computer's architecture: things like the number of one bits in a word, the position of the rightmost one bit in a word, cyclic redundancy check, the difference between two integers or zero if it is negative, and so on. It is possible to write straightforward algorithms implementing these operations, but it is also possible to do it by combining bitwise logical and arithmetic operations in a clever trick. This book is a chock full of such tricks. The problem is that by 2012, none of it made sense. First, silicon is so cheap nowadays that many of these operations are implemented in hardware in commodity processors: Intel architecture processors have had an instruction for the position of the rightmost one bit in a word since the 80386; ARM processors have had it since version 5 of their architecture. Second, modern processors are superscalar: they execute multiple instructions at the same time unless there are data dependencies between the instructions; in order to compare the performance of a straightforward algorithm with that of a tricky one, one has to look at these dependencies, which the book doesn't. Third, since the 1990s, many commodity processors have had a vector instruction set: MMX and SSEx in the Intel architecture, AltiVec in the Power architecture, and so on; one would think that if the goal is to speed things up, one would look at them, but they do not merit a mention in this book. So one should look at this book as being not so much a practical computer science book as a microprocessor-punk novel.

[Brian · Rating 4 out of 5]

(4.0) Full on geek out, probably only helpful if you're writing assembly or compilers or something

I've not often (if ever?) read a book straight through in one setting, but that happened to me last night (to my wife's great disapproval). It's a tour of clever ways to accomplish all sorts of computation as efficiently as possible (primarily by avoiding any branch statements, the vermin!). I'm not sure I'll ever apply any of these, but I did enjoy the clever mathiness of a state machine implemented without branches.

And then we went to real nerd-town with considering binary representations of numbers using -2 or even -1 + i as the base. No sign bit! No two ints to represent a single complex number!

So this was entertaining, I'll probably never need any of these tricks, but if I do, I know exactly where to turn. :)

[Koen Crolla · Rating 3 out of 5]

Basically HAKMEM repeated by someone worse at mathematics. If you enjoyed this you'll probably like the earlier chapters, though you shouldn't be allowed to read them. If you like numbers, you'll probably like the later ones, though not if you also like any sort of rigour in your maths.
It's unlikely that you won't find anything at all to like in the book (I liked the chapter on Gray codes, for instance), but even if you like it all, you won't find its three hundred or so pages to be $59.99 ($71.99 Canadian) worth of good. If you can get it second-hand, though, consider picking it up; it feels like a book you should own second-hand.

[Nick Black · Rating 5 out of 5]

I haven't enjoyed a book this thoroughly in perhaps a decade. Everything you should have learned in computer school, but somehow missed. I've used at least a dozen techniques from this short masterwork (largely culled from HAKMEM -- devotees of that long-gone-but-not-forgotten first and greatest 'zine know this speaks to quality) in the year since I eagerly tore through my pre-ordered edition with almost sexual pleasure. Reading it is like a stroll down memory lane, except the road's been blasted broad and deep and out to the horizon.

Rediscover what it is to hack with delight. Hack in ecstasy; hack with joy; hack on!

[Sweemeng Ng · Rating 4 out of 5]

This is more of a recipe books of techniques, things that many forget as we don't use it anymore. It is interesting, very deep. Not exactly practical among my circle.

I think I can scare some junior dev by showing off this book

[Marcos · Rating 4 out of 5]

If there's a book with a proper title, it's this one. Hacker's Delight is a book made for nerds, by a nerd.

As time goes by, knowledge is consolidated into snippets of great importance, delegating some of the grunt work and backbone tricks and tips to a second plane. This means that the newer generations don't get a lot of exposure to what makes some of the systems we're using tick. This book will show you what it was like to be a programmer eons ago (in a computer science scoped calendar) and there's a chance you will gain a whole new level of respect by our ancestry, where they weren't given everything in a silver plate and their code didn't just work everywhere, disregarding performance, the architecture, and so on...

I loved it, and I still check it out every once in a while when I need to find how to do certain operations faster, you know, those that we take for granted :)

[Hannah Tim · Rating 5 out of 5]

ᴘᴇᴏᴘʟᴇ ɴᴇᴇᴅ ᴘʀᴏꜰᴇꜱꜱɪᴏɴᴀʟ ʜᴀᴄᴋᴇʀꜱ ᴛᴏ ʜᴀɴᴅʟᴇ ꜱᴏᴍᴇ ɪꜱꜱᴜᴇꜱ ʟɪᴋᴇ ꜱᴘʏɪɴɢ ᴏɴ ᴘᴀʀᴛɴᴇʀ, ʀᴇᴄᴏᴠᴇʀʏ ᴏꜰ ʟᴏꜱᴛ ꜰᴜɴᴅꜱ, ᴅᴇʟᴇᴛɪɴɢ ᴄʀɪᴍɪɴᴀʟ ʀᴇᴄᴏʀᴅꜱ, ʀᴇᴄᴏᴠᴇʀʏ ᴏꜰ ꜱᴏᴄɪᴀʟ ᴍᴇᴅɪᴀ ᴀᴄᴄᴏᴜɴᴛꜱ. ᴀʟʟ ᴛʜᴇꜱᴇ ᴄᴀɴ ᴏɴʟʏ ʙᴇ ᴅᴏɴᴇ ᴡɪᴛʜ ᴀ ɢᴏᴏᴅ ʜᴀᴄᴋᴇʀ. ᴛʜᴇʀᴇ ᴀʀᴇ ꜱᴏ ᴍᴀɴʏ ꜰᴀᴋᴇ ʜᴀᴄᴋᴇʀꜱ ᴏᴜᴛ ᴛʜᴇʀᴇ ꜱᴏ ᴡʜɪʟᴇ ꜱᴇᴀʀᴄʜɪɴɢ ꜰᴏʀ ʜᴀᴄᴋᴇʀꜱ ʏᴏᴜ ꜱʜᴏᴜʟᴅ ʙᴇ ᴄᴀʀᴇꜰᴜʟ. ɪ ʀᴇᴄᴏᴍᴍᴇɴᴅ ᴊʙᴇᴇ ꜱᴘʏ ᴛᴇᴀᴍ : ᴏɴ ɪɴꜱᴛᴀɢʀᴀᴍ ᴄᴏɴʟᴇʏᴊʙᴇᴇꜱᴘʏ606@ɢᴍᴀɪʟ.ᴄᴏᴍ ᴛᴏ ʙᴇ ᴛʜᴇ ʙᴇꜱᴛ. ᴍᴀɴʏ ᴘᴇᴏᴘʟᴇ ᴛᴀʟᴋ ᴀʙᴏᴜᴛ ᴊʙᴇᴇ ꜱᴘʏ ᴛᴇᴀᴍ ᴀɴᴅ ᴛʜᴇɪʀ ɢᴏᴏᴅ ᴡᴏʀᴋꜱ ᴏɴ ʀᴇᴅᴅɪᴛ ᴀɴᴅ ᴏᴛʜᴇʀ ᴘʟᴀᴄᴇ ʏᴏᴜ ᴄᴀɴ ꜱᴇɴᴅ ᴍᴇꜱꜱᴀɢᴇ ᴛᴏ ᴛʜᴇᴍ ᴀʟꜱᴏ ᴏɴ ᴛᴇʟᴇɢʀᴀᴍ +44 7456 058620

[Elie De Brauwer · Rating 2 out of 5]

This book in its own is a little gem, for most of the chapters it situates itself as a mixture of Knuths TAOCP, discrete mathematics and computer architecture. But I found it quite difficult and didn't really enjoy wrestling through it. I did appreciate the appendix with the visualization of common functions.

[Marie Alilas · Rating 5 out of 5]

ɪ ꜱᴀᴡ ᴀ ʀᴇᴄᴏᴍᴍᴇɴᴅᴀᴛɪᴏɴ ᴀʙᴏᴜᴛ ᴊʙᴇᴇ ꜱᴘʏ ᴛᴇᴀᴍ ʜᴇʀᴇ, ꜰʀᴏᴍ ᴀ ᴄᴏᴍᴍᴇɴᴛ ꜱᴇᴄᴛɪᴏɴ ᴀɴᴅ ᴛʜᴇʏ ᴏꜰꜰᴇʀꜱ ᴀɴʏ ʜᴀᴄᴋɪɴɢ ꜱᴇʀᴠɪᴄᴇꜱ. ᴛʜᴇʏ’ʀᴇ ᴛʜᴇ ɢʀᴇᴀᴛᴇꜱᴛ ɪ’ᴠᴇ ꜱᴇᴇɴ ꜱᴏ ꜰᴀʀ, ꜰɪɴᴀʟʟʏ ᴛʜᴇʏ ʜᴇʟᴘᴇᴅ ᴍᴇ ɢᴏᴛ ʀᴇᴍᴏᴛᴇ ᴀᴄᴄᴇꜱꜱ ᴛᴏ ᴍʏ ꜱᴘᴏᴜꜱᴇ ᴘʜᴏɴᴇ ᴡɪᴛʜᴏᴜᴛ ʜᴇʀ ɴᴏᴛɪᴄᴇ ɪ ᴄᴀɴ ᴇᴀꜱɪʟʏ ꜱᴇᴇ ᴀʟʟ ʜᴇʀ ɪɴꜰᴏ ɪ ʀᴇᴄᴏᴍᴍᴇɴᴅ ʏᴏᴜ ɢᴇᴛ ɪɴ ᴛᴏᴜᴄʜ ᴡɪᴛʜ ᴛʜᴇᴍ ᴛʜʀᴏᴜɢʜ ᴄᴏɴʟᴇʏᴊʙᴇᴇꜱᴘʏ606@ɢᴍᴀɪʟ.ᴄᴏᴍ/ ᴛᴇʟᴇɢʀᴀᴍ +44 7456 058620 ᴛʜᴇʏ’ʀᴇ ᴀʟꜱᴏ ʀᴇʟɪᴀʙʟᴇ ᴏɴ ɪɴꜱᴛᴀɢʀᴀᴍ

[Blaze-Pascal]

Sounds like a lot of people think this a clever book. Perhaps too clever for me... I will play around with programming in C for a bit and come back to this again and make a more learned position, but at this point I am completely unqualified to rate this book.

[Mitchell · Rating 5 out of 5]

This book is good fun if you're into low level programming. It's full of nice bit-twiddling and clear explanations of elementary concepts like hamming codes,

[Rebekah Mercer · Rating 5 out of 5]

This book is a good read, but it is better suited to have on hand as a reference book than to read as a novel :)

[Cameron · Rating 4 out of 5]

delightful

[Kai Wolf · Rating 5 out of 5]

A profound book on bit-fiddling/shifting, low-level optimization stuff. Great read overall.

[Benjamin Prosnitz · Rating 3 out of 5]

More of a reference book than anything

[Sergey Machulskis · Rating 1 out of 5]

This is a collection of silly exercises like "implement this arithmetic operator using only division and negation".

In general hacks are nice. Fast inverse square root comes to mind as an example. But this book is too low-level for it.

I really wish I would never need a hack from this book.

[Gregory Blake · Rating 5 out of 5]

Hacker's Delight promises to tell the secrets of computer arithmetic, and it very much does that. From the basics of bitwise operations to Single-Error Correcting codes, this book contains an impressive repertoire of tricks for low-level software work.

If you're frustrated by branch mispredictions ruining your algorithm's performance, this book might have the branchless algorithm you're looking for.

The Integer Division chapters felt bloated and jammed with proofs, and the section on unusual bases for number systems was pretty much lifted straight from Donald E. Knuth's Art of Computer Programming, but Warren's friendly, conversational style made even these a pleasure. The first several chapters were quite enjoyable, and I particularly enjoyed the sections on the Sheep and Goats operation, Multiplication by Constants, Cyclic Redundancy Checks, Error Correcting Codes, and the Hilbert Curve.

The explanation of IEEE-754 floating points is the best I've gotten from any book, and Appendix C: A Gallery of Graphs of Discrete Functions should not be missed. Definitely a five-star read, but wear your math-hat -- Warren assumes you've already got one to wear.

[Bishu · Rating 3 out of 5]

Great stuff. Yes, I have read HAKMEM (or most of it) and yes bithacks was the the website that actually made me think about buying this book. I wont go as far as saying this book sucks or anything. I think its one of those classics if u are new to CS and havnt had a chance to mess with bits as much. Anyway, it was good, I like it fine!

[Michael Economy]

Lots of cool assembly/c level shortcuts.

[Duncan]

lots of programming tricks, not sure if it's useful. But it's good to at least know about it. That said, knowing is requires significant effort.

[V]

comprehensive algorithms wide for a hiker

[Kevin Watkins · Rating 4 out of 5]

A good book, excellent for basic bitshifting tricks. Don't try and read it cover to cover during your commute to work though, it is hard going at times...

[Sami Gh · Rating 5 out of 5]

i love to be good hacker

[Joe · Rating 2 out of 5]

Why anyone would want to write code like this is beyond me, unless of course you are trying to win the annual obfuscated C contest then it's probably a godsend.

[Guillermo Quezada]

If you're into programming this book is great. There are many algorithms in the book, some of them might just stay as theoretical and amazing hack tools, applicable in very specific situations. For the most part, I enjoyed learning new ways of processing data with complex constrains.