Bitwise, Byte Foolish?

 

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

To avoid Carnival, Logan is trying to get some plastic surgery from Farrah Fawcett.

In the post-apocalyptic world of Logan’s Run, humans live out cramped lives in a bunker. Because of the crowded conditions, all citizens must submit to Carnival on their 30th birthdays. What do you do on your Carnival day? You and all the other 30 year olds spiral up into the air and get zapped to death.

Sound like a bad deal? It gets worse. The radiation outside has long since subsided, and the rules being enforced are no longer necessary.

I’ve been immersed in JavaScript for the last few years. Every time I’ve read about JavaScript’s bit operations (and it has a very nice set of ops), I’ve been warned that they are “a hack,” and “slow.” This has always bummed me out. I love bits.

But I got to thinking the other day, all these warnings sound like a sort of a Logan’s Run passed-down message from days gone by. With all the cool things that have been going on with JavaScript lately (thanks to Google’s V8 and the various JIT subsystems going into browsers), maybe, just maybe, bitwise operations have sped up enough to be worthwhile. Since some of the JIT compilers are doing type inference, a series of bit operations could, in theory, be done at full speed, without costly implicit type conversions.

Who Needs Bits?

When I started programming (on 8-bit processors), I mostly worked with integers. When floating point numbers became available, I avoided them for years because they were slow. We did as much math as we could with integers and bit operations. Shift left once, and that’s a multiplication by 2. If you wanted to multiply by 10, you’d do a shift left by one (times two) and a shift left by 3 (times eight) and add those results together.

You wouldn’t do math like that any more, but bits are still good as flags. A single JavaScript number (when treated bitwise) can hold 32 boolean flags!

Here’s what I found out. Just about everything I tried was faster with bitwise operations than with other solutions (even in Internet Explorer). No, you can’t usefully replace one multiplication with a series of adds and shifts, but by no means are bitwise operators too slow to be useful.

        k=~~i; //this is much faster
        k=Math.floor(i); //than this

You can lop off the decimal part of a number not just with ~~, but with ^0 and <<0, too. And they are ALL significantly faster, in all modern major browsers, than calling Math.floor().

//break a number in the range 0-65535 into
// low and high bytes

// this is significantly faster
    lo = i & 255;
    hi = i >> 8;

//than this
    lo = i % 256;
    hi = (i-lo)/256;

Don’t discriminate against JavaScript’s bitwise operators. But keep these things in mind…

  1. You have 32 bits to work with when you treat a JavaScript variable as bits. And that top bit is a sign bit (meaning any number with that top bit set is a negative number).
  2. Don’t mistake bitwise for logical operators.
  3. Learn the difference between “-” and “~”.
  4. Remember that >> shifts the sign bit down while >>> shifts a zero into the top bit.

My favorite place to learn about JavaScript bitwise facilities is here: Bitwise Operators.

When should you be using bitwise operators? Obviously, when you want to pack a bunch of flags into one variable. That should be much faster than having an array of flags.

Dealing with the red, blue, and green parts of a color call out for bitwise operators.

And think about using a shift when you want to multiply or divide by a power of 2, while at the same time converting a floating point number into an integer. Two operations for the price of one!

About these ads

17 Comments

  1. Luke Smith said,

    February 9, 2009 at 11:53 pm

    In my experience, I’ve found that bitwise ops, while neat, and perhaps faster for targeted operations usually fall into the “clever code” category. And clever code tends not to be easily maintainable code.

    if (~str.indexOf(other_str)) {
    // other_str wasn’t found
    }

    Sure you can pack multiple flags into a single var, but when would it really be worth it? I’ve not yet come across a problem set that could be solved with a bitset that wouldn’t be much more maintainable with more verbose flags. More code, yes, but the size is offset by future-developer-friendliness. And js performance really isn’t *that* bad for non DOM related code.

    And as twittered, ~~(-10.5) === -10 whereas Math.floor(-10.5) === -11

    That said, Logan’s Run FTW :)

    • Nosredna said,

      February 10, 2009 at 12:00 am

      Points taken, but at least I won’t be afraid to mask anything off based on the incorrect notion that it will be inordinately slow.

      Thanks for the comment.

  2. TNO said,

    February 10, 2009 at 12:05 am

    I’m glad you took the time to test this old claim, I was always curious to how much slower this was supposed to be. I know a number of places this will be useful. (Especially in projecteuler.net)

  3. Nosredna said,

    February 10, 2009 at 12:09 am

    TNO, I have one case in my code where this will help me. And in the future, I’ll keep my eyes open for more.

    Sometimes, the bit solution is more obvious than thinking in bits and doing it another way.

  4. Drakim said,

    February 10, 2009 at 1:06 pm

    Very interesting. In my own tests just the other day, I was comparing >>0 to floor(), and found floor to be faster (FF3 on Ubuntu), but now that you are claiming otherwise, I’m definitely looking into that deeper and more carefully.

    • Nosredna said,

      February 10, 2009 at 2:23 pm

      My tests were on Windows XP. I did a loop from 0 to 65535. Possible that the particular test could make a difference.

  5. Nosredna said,

    February 10, 2009 at 2:54 pm

    Drakim, try something like this with various limits and increments (making sure the script doesn’t time out): In Firefox on XP, the ~~ always wins for me, by various percentages…

    d = new Date();
    for (j = 0; j < 10; j++) {
    for (i = 0; i <= 655350; i+=5.1) {
    m=~~i;
    }
    }
    d2 = new Date();
    t = d.getTime();
    dt = d2.getTime();

    d = new Date();
    for (j = 0; j < 10; j++) {
    for (i = 0; i <= 655350; i+=5.1) {
    m=Math.floor(i);
    }
    }
    d2 = new Date();
    t2 = d.getTime();
    dt2 = d2.getTime();
    alert((dt-t)+” “+(dt2-t2)+” milliseconds”);

  6. Drakim said,

    February 10, 2009 at 3:04 pm

    Ah, but this test is not completely fair, as you are calling Math.floor() which has to look up the function all the way to the global scope.

    Try adding:
    var floor = Math.floor;

    and then modifying “m=Math.floor(i);” to “m=floor(i);”

    for me after the modification, they both take about 450 milliseconds (slightly tilting to the floor method).

  7. Nosredna said,

    February 10, 2009 at 3:09 pm

    Drakim, good point. I have done that in my own time-critical code (for visualizations), but I don’t see it much in code at-large. I should write a blog post about that!

    P.S. Every time I look at your site, it’s STILL under construction. :-)

  8. Drakim said,

    February 10, 2009 at 3:30 pm

    Yeah, I’m really lazy and all my time goes to various JavaScript projects. ><

    Once it gets done, I’ll at least have a lot of content to add.

    The problem with bit operations is that JavaScript doesn’t operate with integers, so before you do a bit operation then the number must first be converted to an integer, and then converted back when it’s done.

    It might be solved in the future with the next big revision of JavaScript which is supposed to allow us to specify the types of variables. Sounds nice for those performance critical tight spots.

  9. Nosredna said,

    February 10, 2009 at 4:08 pm

    >>The problem with bit operations is that JavaScript doesn’t operate with integers, so before you do a bit operation then the number must first be converted to an integer, and then converted back when it’s done.

    Yeah, I get that. But it still seems that bit shifts and masks for the things you traditionally need them for (working with rgb color values, for example) are the way to go in JavaScript. Avoiding them and doing the work with modulo and division does NOT seem the way to go.

  10. mmw said,

    February 21, 2009 at 7:55 pm

    uint16_t hi = i <> 8;

    // (1<> 16;
    uint32_t l = lo & 0xFFFF;

    uint32_t _lo = h <> 16);

    crazy no?

    if you want I wrote this 10 years ago (maybe more) (I did some revisions till 2003 I think, so if it’s not working anymore :) )

    http://plumber.gnu-darwin.org/home/pub/Documents/samples-scripts/stringUtil.js.html

    - tchuss

  11. mmw said,

    February 21, 2009 at 7:57 pm

    Hi please clean up, cause of < < < < you have a parsing problem, because not understanable if this way, everything is dropped

    - tchuss

  12. mmw said,

    February 21, 2009 at 8:00 pm

    uint16_t hi = i << 8;
    uint16_t lo = i >> 8;

    // (1<<8)

    uint32_t h = hi >> 16;
    uint32_t l = lo & 0xFFFF;

    uint32_t _lo = h << 16;
    int32_t _hi = l >> 16);

  13. March 20, 2009 at 5:42 pm

    You touched upon this with the warning about having 32bits, but I just got caught out using ~~ instead of Math.floor when working with large numbers.

    ~~2147483647 == 2147483647

    But…

    ~~2147483648 == -2147483648

    and…

    ~~2147483649 == -2147483647

    Etc etc.

  14. unscriptable said,

    April 13, 2010 at 8:23 pm

    I just got flogged by the 32-bit issues recently, myself, while doing crc-32 in javascript. Wish I saw your blog post first. :(

  15. Larry Battle said,

    March 15, 2011 at 10:10 pm

    After reading this blog, I made a tutroial on javascript bitwise operations.
    You can find it here. Javascript Binary Operations

    “Remember that >>shifts the sign bit down while >>> shifts a zero into the top bit.” – Very helpful tip.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: