Skip to content

Hacker’s Delight

x + y = (x XOR y) + (x & y)<<1

It's longhand addition: the sum with carries ignored, plus the carries. Why not just use a normal adder? This equation still has an addition operation. However, this reduces the probability of a carry operation by about half (assuming binary numbers with each bit independently equally likely to be either 0 or 1).

It's not useful, but it's cool. This whole book is 300 pages of such tricks, few of which I expect ever to use, but all of which trigger little explosions of happiness when I figure out how they work. If you've ever considered bit-twiddling without immediately assuming it's a euphemism, you'll like this book.

Hacker’s Delight, Henry S. Warren, Jr. (Amazon)

RSS feed

Comments

No comments yet.

Sorry, the comment form is closed at this time.