Did you miss your activation email?

• April 26, 2018, 06:17 PM
• Proudly celebrating 13 years online.
• Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.

### Author Topic: Bitwise gems - fast integer math  (Read 3488 times)

#### gjehle

• Member
• Joined in 2006
• Posts: 286
• lonesome linux warrior
##### Bitwise gems - fast integer math
« on: June 28, 2007, 03:42 AM »
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);

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!

#### f0dder

• Charter Honorary Member
• Joined in 2005
• Posts: 9,100
• [Well, THAT escalated quickly!]
##### Re: Bitwise gems - fast integer math
« Reply #1 on: June 28, 2007, 05:32 AM »
"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.
- carpe noctem

#### Eóin

• Charter Member
• Joined in 2006
• Posts: 1,401
##### Re: Bitwise gems - fast integer math
« Reply #2 on: June 28, 2007, 07:03 AM »
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

• Charter Honorary Member
• Joined in 2005
• Posts: 9,100
• [Well, THAT escalated quickly!]
##### Re: Bitwise gems - fast integer math
« Reply #3 on: June 28, 2007, 07:34 AM »
- carpe noctem

#### gjehle

• Member
• Joined in 2006
• Posts: 286
• lonesome linux warrior
##### Re: Bitwise gems - fast integer math
« Reply #4 on: June 28, 2007, 09:39 AM »
"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

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

true indeed