Bitwise gems - fast integer math

[gjehle]

Fast modulo operation using bitwise AND

If the divisor is a power of 2, the modulo (%) operation can be done with:
modulus = numerator & (divisor - 1);
This is about 600% faster.

[Select]

x = 131 % 4;

//equals:
x = 131 & (4 - 1);

Every programmer should know about the simple shift-left, shift-right for base2 multiplication and division (if you don't, you're missing something).
This page, however, lists a couple of real gems (as the title suggests) like the one quoted above.
Enjoy!

http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/

[f0dder]

"This is about 600% faster." - I love people making bold claims without making any reference to which platform they tested it on :] (ah, following the link they mention AS3 - flash actionscript?)

Bitwise math is good to know, though. I generally don't do it for highlevel code, but once there's a bottleneck, it can be worth it (usually ends up in assembly code then). Keep in mind that decent compilers know a bunch of these tricks already, which is good reason you wouldn't do ">> 2" to divide by four in C.

[Eóin]

I'd highly recommend everyone learning why those gems work. It would teach you a lot about how computers represent numbers and that could lead you to understand when and where those trick are really applicable.

[f0dder]

Sage advice, Eóin.

[gjehle]

"This is about 600% faster." - I love people making bold claims without making any reference to which platform they tested it on :] (ah, following the link they mention AS3 - flash actionscript?)
[...]
Keep in mind that decent compilers know a bunch of these tricks already, which is good reason you wouldn't do ">> 2" to divide by four in C.

-f0dder (June 28, 2007, 05:32 AM)

hehe yes! exactly
the only reason why some of those bitwise ops are that much faster has to be a bad intermediate compiler / interpreter.
after all you want the script to start running, not compile for 5 minutes.
nevertheless, this list shows how to do some nice operations in bitwise and being who i am (someone who enjoys obfuscated c and perl and fancy/different ways to approach simple tasks) i appreciate websites like this one just for the fact that they list the operations ;-)
it's like a work of art
or maybe i already studied too much comp sci :x

I'd highly recommend everyone learning why those gems work. It would teach you a lot about how computers represent numbers and that could lead you to understand when and where those trick are really applicable.

-Eóin (June 28, 2007, 07:03 AM)

true indeed