Main Area and Open Discussion > Living Room

Bitwise gems - fast integer math

(1/1)

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.


--- ---x = 131 % 4;

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

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)
--- End quote ---

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)
--- End quote ---

true indeed

Navigation

[0] Message Index