topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • Thursday March 28, 2024, 2:31 pm
  • Proudly celebrating 15+ 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.
  • donate

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

gjehle

  • Member
  • Joined in 2006
  • **
  • Posts: 286
  • lonesome linux warrior
    • View Profile
    • Open Source Corner
    • Read more about this member.
    • Donate to Member
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);
This is about 600% faster.

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,153
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
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
    • View Profile
    • Donate to Member
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,153
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Bitwise gems - fast integer math
« Reply #3 on: June 28, 2007, 07:34 AM »
Sage advice, Eóin.
- carpe noctem

gjehle

  • Member
  • Joined in 2006
  • **
  • Posts: 286
  • lonesome linux warrior
    • View Profile
    • Open Source Corner
    • Read more about this member.
    • Donate to Member
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.

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.

true indeed