Checking if number is even by looking at the last bit - are there any other "tricks" like this one?

Question

Recently I discovered, that if I need to see if variable is even ( or odd ), I could just see if last bit of variable equals 0. This discovery, when implemented, replaced few modulo 2 calculations and thus, whole function ran faster.

Are there any other "tricks" like this one, where working with bits could replace other calculations, leading to improved function execution time?

Answer 1

I doubt that replacing the use of modulo-two calculations by the equivalent bitwise operation produced faster execution times. Any C++ compiler worth its grain of salt will compile n % 2 and n & 1 to identical machine instructions.

Beware of using bit-twiddling hacks as an optimization. First, it's not always clear that the function you are optimizing is a bottleneck. Second, the resulting code is usually harder to maintain and more likely to be incorrect or have subtle bugs. This is what is meant in the famous quote Knuth quote "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." Save your effort.

If you truly must pursue this subject, Bit Twiddling Hacks contains a nice list of interesting hacks.

Answer 2

Well, there is a great book on this topic: Hacker's Delight (Google books).

On Amazon.com: Hacker's Delight.

Answer 3

There's a large repository of bit twiddling hacks here

Answer 4

There are lots. One online "collection" you can start with is http://www-graphics.stanford.edu/~seander/bithacks.html

I would highly recommend againts using bit twiddling tricks in code unless the performance boost is absolutely, definately, 100% needed. These tricks are very unreadable and have this "no way this works" feel to them, so when you are trying to figure out a bug they are effective time wasters for whoever it is who is trying to debug the code.