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 thoughts on “Bitwise gems – fast integer math”

  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. 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.

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

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

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

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

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

  7. 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

  8. 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.

  9. 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:
    0x4000 * 0x40000 == 0 (overflow 0x100000000)
    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..

  10. 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;

  11. 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.

  12. 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?

  13. 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.

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

  15. 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.

  16. 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.

  17. 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.

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

  19. 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)

  20. 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 >>

  21. 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.

  22. 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.

  23. Hi ,

    Could I know your testing environment?

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

  24. 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.

  25. 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 = 0x336699;
    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 = 0x88;
    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!

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

  27. 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!

  28. 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!

  29. 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.

  30. 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;

Comments are closed.