Checking the number, even if you look at the last bit - are there any other "tricks" like this?

Question

I recently discovered that if I need to see if a variable is even (or odd), I can just see if the last bit of the variable is 0. This discovery, when implemented, replaced several computations of modulo 2 and thus whole function faster.

Are there other "tricks" like this one where working with bits can replace other calculations, which will lead to an improvement in the execution time of the function?

Answer 1

I doubt that replacing the use of modulo-two computations with an equivalent bitwise operation caused faster execution time. Any C ++ compiler deserving its salt will compile n % 2 and n & 1 to identical machine instructions.

Beware of using bit twiddling hacks as optimizations. First, it’s not always clear that the function you are optimizing is a bottleneck. Secondly, the resulting code is usually more difficult to maintain and most likely to be incorrect or have subtle errors. This is what is implied in Knut’s famous quote, “We must forget about little efficiency, say, about 97% of the time: premature optimization is the root of all evil.” Save your efforts.

If you really should pursue this topic, Bit Twiddling Hacks contains a nice list of interesting hacks.

Answer 2

Well, there is a great book on the subject: Hacker Delight (Google Books).

On Amazon.com: Hacker Delight .

Answer 3

There is a large repository of bit tricks.

Answer 4

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

I would highly recommend repeating using bit tricks using tweets in code, unless performance improvements are necessary, 100% necessary. These tricks are very unreadable, and it doesn’t work for them, so when you try to find an error, they are effective for the time when someone tries to debug the code.

Answer 5

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

Although it would be helpful to understand all such tricks, it should be nice to know that the compiler (or the compiler author) is doing the hard work to get all the optimization options.

What you should remember if you use constants and work with permissions 2, optimization is more likely, since compilers use the capabilities of the machine binary operator.

---

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

To this end, the training tricks you link to here will be very useful .
However, cryptic coding with complex operations stuck together
(say, to do all this in less bytes of source code) is not good.

It would be nice to know that you can change two 32-bit variables in place, without a third temporary variable, using XOR operations. But it would be more useful to know that hto cross-compilation requires processing large and small numbers for 2/4 byte variables and bit fields .

Speaking of bit fields, it recalls another talk about glass-likeness about their popularity . It would also be a good read (although not completely related to your question).

---

To summarize, I fully learn with you what tricks can be done. I want to use them to make my code more efficient - and I firmly feel that these will be such concepts as what programmers can do to improve cache optimization , for example, which will help to improve implementation.

Answer 6

Here's a neat trick. When storing a date in a database field that requires intensive search, do not save the date format in a format, but save it as an integer in the format YYYYMMDD. Databases can search for integers much faster than date structures.

Answer 7

I thought the “bit flags” were the first time that I saw them: http://www.infernodevelopment.com/bitwise-and-flags