Bitwise gems – fast integer math

Bitwise operators are very fast in AS3, so here is a small collection of code snippets which can speed up certain computations. I won’t explain what bit operators are and how to use them, rather pointing to an excellent article hosted on gamedev.net: ‘Bitwise Operations in C’.
If you know any good tricks that are not included here, feel free to leave a comment or send me an email. All benchmarks were done in AS3.

Left bit shifting to multiply by any power of two

Approximately 300% faster.

x = x * 2;
x = x * 64;

//equals:
x = x << 1;
x = x << 6;

Right bit shifting to divide by any power of two

Approximately 350% faster.

x = x / 2;
x = x / 64;

//equals:
x = x >> 1;
x = x >> 6;

Number to integer conversion

Using int(x) is 10% faster in AS3. Still the bitwise version works better in AS2.

x = int(1.232)

//equals:
x = 1.232 >> 0;

Extracting color components

Not really a trick, but the regular way of extracting values using bit masking and shifting.

//24bit
var color:uint = 0x336699;
var r:uint = color >> 16;
var g:uint = color >> 8 & 0xFF;
var b:uint = color & 0xFF;

//32bit
var color:uint = 0xff336699;
var a:uint = color >>> 24;
var r:uint = color >>> 16 & 0xFF;
var g:uint = color >>>  8 & 0xFF;
var b:uint = color & 0xFF;

Combining color components

‘Shift up’ the values into the correct position and combine them.

//24bit
var r:uint = 0x33;
var g:uint = 0x66;
var b:uint = 0x99;
var color:uint = r << 16 | g << 8 | b;

//32bit
var a:uint = 0xff;
var r:uint = 0x33;
var g:uint = 0x66;
var b:uint = 0x99;
var color:uint = a << 24 | r << 16 | g << 8 | b;

Swap integers without a temporary variable using XOR

Pretty neat trick, it is explained in detail in the link at the top of the page. This is 20% faster.

var t:int = a;
a = b;
b = t;

//equals:
a ^= b;
b ^= a;
a ^= b;

Increment/decrement

This is much slower than the pre/post decrement operator, but a nice way to obfuscate your code ;-)

i = -~i; // i++
i = ~-i; // i--

Sign flipping using NOT or XOR

Strangely enough, this is 300%(!) faster.

i = -i;

//equals
i = ~i + 1;

//or
i = (i ^ -1) + 1;

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);

Check if an integer is even/uneven using bitwise AND

This is 600% faster.

isEven = (i % 2) == 0;

//equals:
isEven = (i & 1) == 0;

Absolute value

Forget Math.abs() for time critical code. Version 1 is 2500% faster than Math.abs(), and the funky bitwise version 2 is again 20% faster than version 1.

//version 1
i = x < 0 ? -x : x;

//version 2
i = (x ^ (x >> 31)) - (x >> 31);

Comparing two integers for equal sign

This is 35% faster.

eqSign = a * b > 0;

//equals:
eqSign = a ^ b >= 0;

Fast color conversion from R5G5B5 to R8G8B8 pixel format using shifts

R8 = (R5 << 3) | (R5 >> 2)
G8 = (R5 << 3) | (R5 >> 2)
B8 = (R5 << 3) | (R5 >> 2)

89 Comments

  1. Nice article, but your alternate absolute value isn’t exactly right, Math.abs() should return the input number with a positive sign – version 1 only returns 1 or -1. Version 2 only works with integers, that’s not a bug as such but perhaps worth mentioning.

  2. thanks for the hint, I have corrected the typo – it was the code for extracting the sign, not for the absolute value. And yes everything only works with integers.

  3. Cool post. Nice redesign by the way!

  4. Fast color conversion using shifts:

    When promoting a R5G5B5 color value to R8G8B8 most just left shift the 5 bit color component value three places. This is will lead to incorrect results. A 5-bit value of 31 (denoting 100%), shifted left three places would be 248. The correct value should be 255.

    A quick way to do this using bitwise operations is to perform the left shift, then copy the upper three bits into the lower, zeroed bits after the shift:

    R8 = (R5 > 2)

    See “Hacker’s Delight” by Henry S. Warren Jr. for more on bitwise operations and integer math.

  5. Looks like my post got hosed. The code bit should be:

    R8 = LogicalOR(LeftShift(R5, 3), RightShift(R5, 2))

  6. Thank you, I have added it to the post so it’s more readable. I also included code for extracting/combining ARGB color components

  7. Best blog post I’ve found in a while. Thanks for the tricks :)

  8. cbirkhold

    x = x / 2;
    //equals:
    x = x >> 1;

    Has one problem: -1 >> x will be -1 rather then 0

  9. I think you will be VERY interested in this article by Andre and me:

    http://blog.andre-michelle.com/2007/weird_behavior_of_numbers_in_as3/


    // be confused, very confused...
    trace( getQualifiedClassName(uint.MAX_VALUE) )
    trace( getQualifiedClassName(uint.MAX_VALUE>>1) )

    Using uints for 32-bit color (RGBA) values will almost always use Number instead of uint.

    Check the comments in andre’s post for the explanation of this (sad!) fact.

    This also explains why some people have seen strange performance problems with uint/int: even though you think you’re handling a (u)int, it might actually be a number!


    // be afraid, be very afraid
    var color:uint = 0xff336699;
    trace( getQualifiedClassName(color) );

    greetings,

    – bram

  10. trace( getQualifiedClassName(uint.MAX_VALUE) )
    trace( getQualifiedClassName(uint.MAX_VALUE>>1) )

    this is perfectly valid – the signed bitshift operator works only with signed 32bit integers, so MAX_VALUE and 1 are both converted to signed integers first, and so the result is also a signed integer. For unsigned integers use >>>.

    so: trace( getQualifiedClassName(uint.MAX_VALUE>>>1) now outputs NUMBER

    also, performance loss occurs only when converting between data types.

  11. Hello! Good Site! Thanks you! pojoscyufy

  12. Comparing two integers for equal sign:

    shouldn’t the example be something like
    eqSign = ((a>=0) && (b>=0)) || ((a eqSign = a * b > 0;
    is actualle not very accurate.
    lets assume the machine has 32bit-registers:
    0×4000 * 0×40000 == 0 (overflow 0×100000000)
    using a*b>=0 won’t help, because than a zero in either variable makes the product zero, indicating different sign.

    > //equals:
    > eqSign = a ^ b > 0;
    shouldn’t that be
    eqSign = a^b >= 0;
    ?
    otherwise 2^2==0 means 2 and 2 don’t have the same sign..

  13. example:
    eqSign = ((a >= 0) && (b >= 0)) OR ((a GREATER 0) && (b GREATER 0));

    faster, but inaccurate:
    eqSign = a TIMES b GREATER 0;

    Even faster and more accurate:
    eqSign = a ^ b >= 0;

  14. thanks, I fixed it in the article.

  15. You are aware that if you’re using a good modern compiler that these will become the exact same machine code as the original mathematical operations, right? The compiler changes any convenient algebraic operations to bit shifts.

    So the important thing to do to optimize your code isn’t to use bit shifting, it’s to make sure you’re using a good compiler, and that you try to use powers of two when doing division or multiplication, so that the compiler can use bit shifting in the machine code.

  16. It cut off my comment. Nice. Here’s what I meant to send (LT being less than…): Using what I just read, wouldn’t it be faster to do something like this for absolute values: i = x LT 0 ? (~x + 1) : x; Or, is that not possible/faster? If so, why?

  17. good idea, I didn’t see that ;-) but ‘i = x < = 0 ? (~x + 1) : x' is not faster than 'i = x < 0 ? -x : x'. I can't tell why, you simply have to try things out and do benchmarks to find the best solution because you don't know how the flash compiler works and how it puts the byte code together.

  18. se_godfaser

    theres a mistake at ‘Extracting color components’ (32-bit). you wrote three times ‘

  19. se_godfaser

    hmmm my comment got cut off …
    what i wanted to say is you wrote ‘

  20. se_godfaser

    hmm sorry for triple post but seems as the triple shift would be an endsign or so. anyway the code at ‘Extracting color components’ doesnt work but it is possibly just a writing mistake.

  21. thanks, I know what you mean, it’s fixed now :-)

  22. Wonderful article, thanks a lot!

  23. On the same note, I put together a tester to test the different opperations on the differnt types at

    http://jlgauthier.com/blog/?p=3

    I found that that performance varies on copile / player and os. Linux is not liking the uint at all.

  24. Awesome tips man, thanks a lot.

    Only one question. If some of these bitwise operations are so much faster than the standard mathematical operands, how come Flash doesn’t automatically convert the code like this when you compile? Surely the devs were aware of these tricks.

  25. modern compilers in other languages like c++ do a lot of optimizations behind the scenes, but the as3 compiler simply doesn’t offer this kind of optimization, so you have to do it yourself in most situations.

  26. Hello!

    Your post is very useful for me but I have a problem with your modulo operation… For example :

    // returns 1
    trace(7 % 6);
    // returns 5
    trace(7 & (6 – 1));

  27. hi sappy, this only works if the divisor is a power of 2. in your example the next largest power of 2 would be 8 (2^3): 7 & (8 – 1)

  28. oh ok, so sapppy I am… it was written but I didn’t read very well… Thanks!

  29. Just want to say thanks for this… I just modified some ENTER_FRAME code on a mouse-driven Perlin noise operation and it has smoothed everything out on older machines.

    Nice work – thanks for sharing the wonders of the little pointy brackets >>

  30. One thing I’m looking for… you only explicity define the variable type in your examples for color math. For my benefit and that of future visitors, it would be great if there was a note regarding int vs. uint for bitwise ops.

  31. Hello.

    Someone knows how to get very simply and quickly the position of the last bit equalling 1 in an int ?

    Actually I found 2 solutions:

    // simple but slow
    n.toString(2).length;

    and

    // fast but complex
    var l:int;
    while (n) { n >>= 1; l++; }

    So the first is very slow, and the second needs to create a variable and while loop.

    If someone knows a manner to get this position as simply as the first and as quicly as the second, you’re the king!

    Thx.

  32. dimumurray

    Here’s a good collection of bit-wise hacks, I’m not sure how well they carry over to AS3 but it’s nice to see how these hacks work regardless:

    http://graphics.stanford.edu/~seander/bithacks.html

  33. Three XORs for swapping integers is optimal choise.
    And how do you like this short style?
    b^=a^=b^=a;

  34. Hi ,

    Could I know your testing environment?

    which IDE , flash player or Browser you used to test?

  35. This was tested with the standalone flash player 9 on windows. but I assume that nowadays the results are out of date and differ greatly.

  36. Awesome post, came here off google numerous times over the past couple years. :)

    Just wanted to add this comment expanding on your tip on how to extract/combine RGB and ARGB color components; this is how you can change a specific color component:

    // 24bit
    var color:uint = 0×336699;
    var r:uint = 0xFF, g:uint = 0xFF, b:uint = 0xFF;
    color = (color & 0x00FFFF) + (r << 16); // change red
    color = (color & 0xFF00FF) + (g << 8); // change green
    color = (color & 0xFFFF00) + b; // change blue

    // 32bit
    var color:uint = 0xFF336699;
    var r:uint = 0xFF, g:uint = 0xFF, b:uint = 0xFF, a:uint = 0×88;
    color = (color & 0xFF00FFFF) + (r << 16); // change red
    color = (color & 0xFFFF00FF) + (g << 8); // change green
    color = (color & 0xFFFFFF00) + b; // change blue
    color = (color & 0x00FFFFFF) + (a << 24); // change alpha

    If nothing else now I’ll find this the next time I google for it and wind up here. :)

    Cheers!

  37. My addition.

    From r8g8b8 to r5g6b5:
    c16 = ((c & 0xF80000)>>8) | ((c & 0xFC00)>>5) | ((c & 0xF8)>>3);

    From r5g6b5 to r8g8b8:
    rgb = ((c & 0xF800) << 8) | ((c & 0x7E0) << 5) | ((c & 0x1F) << 3);

  38. Good article. People are in general dumbfounded by bitwise operators, but they are in fact extremely useful.

  39. Amazing
    I really like it, would like to be more info here

  40. This post is amazing, and I’m very glad to see that someone has taken the time to do this. However, I thought I should let you know that “eqSign = a ^ b >= 0;” doesn’t actually check to see if two values are equal in value. I’m guessing it was probably a typo…but just in case.

    Say you have the binary values for 10 (1010) and 7(0111). XORING these two values together will provide the following results:

    1010 (10)
    ^0111 (7)
    _____
    1101 (13)

    SO…13(1101) is greater than 0, but 10 and 13 are obviously NOT equivalent in value. Meaning, that the solution should be “eqSign = ((a^b) == 0);”, rather than the suggested version posted above.

    Keep up the great work!

  41. Performance is everything especialy in flash

    If you have any flash files you would like to share, come upload them to Flash Source Codes

  42. Hey dude, this is a really interesting article, thank you very much for sharing these kind of experiments. I think the biggest problem people have is that they always try to use bitwise operators on top of the logic they already have done and it is completely wrong, it needs to be done the other way round, we must build our logic based on these bitwise operators from the very beginning and then our code will look and run completely different. I’ve been involve in a project for validating poker hands using lots of these bitwise operators techniques and I wrote a short article speaking about it, just in case you’re interested on it, it is called The fastest poker hands evaluator ever, thanks for sharing, cheers!

  43. I am curious how you are running these tests. I realize your tests are several years old but I figure that performance would actually have improved in subsequent player builds.

    Check this out:
    http://jacksondunstan.com/articles/840

    Why the discrepancies?

  44. My benchmarks are totally outdated (2007!) so I’m not sure if the results are still valid.

  45. Bill_BsB

    Hi there!
    This post is an amazing reference for any AS3 developer (actually, any developer I suppose)!

    Could you give us any update on these benchmarks? After all, it’s already 2011 and we are in Flash Player 10.2! I suppose Adobe made some improvements on their runtime.

    Cheers.

  46. Just realized how to do bitwise rounding, ceiling, and floor functions… kinda obvious after thinking about it, but none-the-less wanted to post to my favorite article on bitwise operations;

    Math.round(n) === (n + 0.5) >> 0;
    Math.ceil(v) === (v + 1) >> 0;
    Math.floor(v) === v >> 0;

Trackbacks/Pingbacks

  1. [...] Bitwise Operation in AS3 Published May 10th, 2007 Actionscript 3.0 , Web developer , Flex , Flash Examples and comparison between bitwise operations and regular operations show performance superiority on behalf of bitwise option. Good work from polygonal [...]

  2. [...] when reading another excellent polygonal labs post on benchmarks and performance (this one is great as well concerning faster operations using bit shifts or alternate ways to eek out…) where he wisely advises to use signed int for loops or iterations rather than uint where needed [...]

  3. [...] Bitwise mathematics and shortcuts In my last post I alluded to highly-optimal maths using bitwise (logical) operators, just now (whilst trying to further my own understanding) I found this excellent article on the subject: Polygonal Lab’s Tutorial. [...]

  4. [...] 3: Faster Integer Math – Bitwise Operators Several months ago, I stumbled upon a great resource for bitwise operators in AS3. Bitwise math is available in many languages, but this one looks at it from an AS3 [...]

  5. [...] If you’re not familiar with bitwise operators I suggest you check out Polygonal Labs’ Bitwise Gems: Fast Integer Math. Done? Great. Okay, on with our discussion. I hope this stuff makes sense because this is my first [...]

  6. [...] Polygonal Labs shows some cool tricks to help speed up your code (C, PHP, AS, etc…). [...]

  7. [...] AS3 Interesting Numeric Storage Behavior Andre Michelle: Weird behavior of numbers in as3 Michael Baczynski: Bitwise gems – fast integer math Michael Baczynski: Int, uint and number data type conversion Sho Kuwamoto: Avoid ints in [...]

  8. Buenas Practicas…

    Introduccion El fin de esta pagina es agrupar todas la Buenas Practicas que fuimos recolectando de distintas fuentes para evitar problemas de performace/memory leaks en aplicaciones Flex/AIR…….

  9. [...] reading:Joa Ebert on optimizationSpeed tests over on OS FlashBitwise gems at Polygonal Posted by Rob Filed in AS3 Speed Benchmarking, Actionscript 3.0, [...]

  10. [...] world. I wanted to share a link to this Polygonal labs post about using bitwise operators to optimize performance in Actionscript 3.0. It’s about a year and a half old, and I haven’t tested out the statements made, but I [...]

  11. [...] By thepugilist Hello world. I wanted to share a link to this Polygonal labs post about using bitwise operators to optimize performance in Actionscript 3.0. It’s about a year and a half old, and I haven’t tested out the statements made, but I [...]

  12. [...] This article and this article on bitwise math and manipulation [...]

  13. [...] world. I wanted to share a link to this Polygonal labs post about using bitwise operators to optimize performance in Actionscript 3.0. It’s about a year and a half old, and I haven’t tested out the statements made, but I [...]

  14. [...] do código dão um excelente ganho de desenpenho. Mais dicas sobre operadores de bits em um post bitwise gems fast integer math do [...]

  15. [...] Bitwise gems – fast integer math [Polygonal Labs] [...]

  16. [...] Bitwise gems for fast math [...]

  17. [...] Bitwise tricks Bitwise maths on wikipedia Boolean algebra on wikipedia polygonal labs bitwise gems [...]

  18. Buenas Practicas…

    Introduccion El fin de esta pagina es agrupar todas la Buenas Practicas que fuimos recolectando de distintas fuentes para evitar problemas de performace/memory leaks en aplicaciones Flex/AIR…….

  19. [...] version from the original version by Po-Han Lin is the replacement of Math.abs with a well-known bitwise trick for AS3. The static Math.abs call would certainly be a performance [...]

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

  21. [...] I found great article in Polygonal.de blog about useful bitwise operations and attempted to determine how effective those [...]

  22. [...] Integer math: http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/ If you constantly have to measure items for display (positions etc…) it can have a lot of [...]

  23. [...] nice little tips for speeding up Math calculations in Flash by using bitwise maths which I found on labs.polygonal.de. The Math.abs function was one of the most improved and helped speed things up. static public [...]

  24. [...] http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math/ ??????????? No Related Post ???????????10??????Social Game????? ——?????DAU?Social Game?????ppt? ????????SmartFoxServer,??flash????as3.0 ?????? [...]

  25. [...] Ok, so Math has been something which I keep posting about but I’m always coming across ways of speeding things up. This time is using Bitwise Maths, which i found on labs.polygonal.de. [...]

  26. [...] Bitwise gems – fast integer math [...]

  27. [...] ????: olygonal labs » Bitwise gems – fast integer math [...]

  28. [...] is a good explanation of colour components and how to use bitwise operators to manipulate them: http://lab.polygonal.de/2007/05/10/bitwise-gems-fast-integer-math. It’s faster than using the objects but you can safely use the android methods [...]

  29. [...] Pour des astuces liées à l’optimisation des nombres, rendez-vous sur lab.polygonal.de. [...]

  30. [...] 03-05-2011 Bitwise gems – fast integer math [...]

  31. [...] math that are faster in general, such as bit shifting numbers for squares and dividing by squares, here is a great article explaining some bit shift math and the reasoning behind [...]

  32. [...] Bitwise gems – fast integer math [...]

  33. [...] nice little tips for speeding up Math calculations in Flash by using bitwise maths which I found on labs.polygonal.de. The Math.abs function was one of the most improved and helped speed things up. static public [...]

  34. [...] of my favorite posts in the last few years was Bitwise Gems in AS3 by Polygonal Labs, an article inspired by Bitwise Operations in C on Gamedev which goes into even [...]

Get Adobe Flash player