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

Question

Hello,

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

It may be useful to note that when C++ sees a modulo 2 operation as %2, it usually optimizes without you doing bitwise operations.

While it would be enlightening to understand all such tricks, it should be pleasing to know that the compiler (or the compiler writer) does hard work to get all optimizations possible.

What you should remember is, if you use constants and work in powers of 2, optimizations are more likely since the compilers leverage the machine's binary operator abilities.

---

Going further, I would suggest gaining knowledge of how systems work at low level.

To that end, learning tricks you refer to here would be very useful.
However, cryptic coding with complicated operations jammed together
(say, to do it all in less number of source code bytes) is no good.

It may be good to know that you can swap two 32-bit variables 'in place', without a third temporary variable -- using XOR operations. But, it would be tons more useful to know hhow cross compilation requires big-endian and little-endian handling for 2/4 byte variables and bit fields.

Talking about bit-fields, reminds me of another stackoverflow conversation on their popularity. Would also be good reading (though not entirely related to your question).

---

To summarize, I am totally with you in learning what tricks can be done. I want to use them to make my code perform better -- and, I strongly feel it will be concepts like, what can programmers to do make better cache optimization, for example, that will help making better implementations.

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

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 5

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.

Answer 6

Recently I tried both % 2 and & 1 with -O3 and it run faster with % 2. I'm not sure what compiler did but it was better than my idea :). The speed difference was about 5%.

Answer 7

Here's a neat trick. When storing a date in a database field which requires heavy searching, don't store the date in date format, instead store it as an integer in YYYYMMDD format. Databases can search integers much faster than date structures.

Answer 8

I thought "bitwise flags" were kinda neat the first time I saw them: http://www.infernodevelopment.com/bitwise-and-flags