Former conversations:

http://news.ycombinator.com/item?id=2570269

http://news.ycombinator.com/item?id=3452408

http://news.ycombinator.com/item?id=513935

http://news.ycombinator.com/item?id=2630593

http://news.ycombinator.com/item?id=4590134

http://news.ycombinator.com/item?id=86419

It's a little known fact that >> in C++ (and I suspect in C as well) on a signed type is not guaranteed to be an arithmetical shift. It's up to the implementation and most implementation choose arithmetical shift for signed and logical shift for unsigned but this does not mean that all the implementations do this. So some of this tricks are contingent on the particular implementation specific behavior.

An oldie but a goodie.

Mandatory warning: please don't use those unless you really know what you're doing. Most modern CPUs have instructions for computing all of that stuff and the compiler will try to use them. Those clever hacks might actually hurt both readability and performance if they're misused.

Typically on PC architectures (and even on most modern embedded systems) you shouldn't have to use those hacks.

I've used similar techniques (such as reciprocal multiplication, which is not mentioned on this page) to provide a significant speed advantage for some code on ARM systems. Actual performance-sensitive code, such as the core routines video codecs, is still written in assembly language or with intrinsics.

On a similar note:

http://www.amazon.com/gp/product/0321842685/ref=s9_simh_gw_p...

While we're posting Amazon links,

http://www.amazon.com/Art-Computer-Programming-Combinatorial...

has a fascinating 200+ page section on Boolean and bitwise tricks and techniques (Knuth: "A trick is a clever idea that can be used once, while a technique is a trick that can be used at least twice.").

I think the real value of these hacks is to understand how and they work rather than the possible efficiency gains they may give. Sure, sometimes you just have to get the gains, but these days, on modern platforms this is hardly ever the case.

But man, if you think you know how to deal with the binary and bitwise operations, please take some time to go through all of the hacks and examine how they work. It's quite possible you learn something new and interesting, which may have surprising applications elsewhere.

Classic compilation. Always check for cpu builtin functions (rtfm gcc) first though when you need this kind of optimization "in real life."

Strange, I was using this the other day for the TI Launchpad-based project I'm working on.