Sunday, March 24, 2013

JavaScript: The less known parts. Bitwise Operators.

'JavaScript: The less known parts' chapters:
1. Bitwise Operators
2. Storage
3. Dom Mutations

Most of us probably use JavaScript every day - in my case it's building a mobile operating system in my daily job, preparing crazy and ridiculous demos for various conferences or run personal projects in my free time (mostly games). But even with years of experience (probably because the language itself is full of weird quirks and unintuitive patterns), from time to time I'm still getting surprised with new crazy hacks, techniques or workarounds. I want to put most of those things in one place and publish one every Monday - for last couple of years I wasn't really active on the blog, it's time to change this. First - bitwise hacking.


Bitwise operators

Most of us know know that there are some bitwise operators in JS. Every number has it's own binary representation, used by those operators. To check dec number's binary value, we use .toString() method with base argument - '2' for binary:


There are seven different bitwise operators. Assuming that variable a is equal to 5, and b is 13, those are actions and results of their operations:


Sometime we even use Bitwise OR as equivalent of Math.floor():


It has the same effect as double NOT operator (my favorite rounding solution since I first heard about it on Damian Wielgosik's workshop couple of years ago).


What about other real life examples of bit chaking? For instance, we can convert colors from RGA to Hex format:


We can also simply check which number in a pair is smaller (like Math.min) or bigger (Math.max):


Of course since Math library is really well optimized nowadays, using those hacks doesn't make any sense. But what about variables swap? Most common solution is to create a temporary variable to achieve that, what is not really efficient. It's simpler to use bit operations here:


Even with 'Pythonish' variable swap introduced in JavaScript 1.7, bitwise solution is the fastest way to achieve that.
JSPerf test [here]:


Great place to learn more bit-tricks to make your JS app: Sean Eron Anderson's site [Stanford PhD].
Do you know and use any more binary tricks in your JavaScript projects?

18 comments:

  1. Cool overview!

    I would like to point out that the delete operation in the 'temp variable' JSPerf case is what's slowing it down. The delete operation isn't valid anyway -- it won't succeed in function context and will return false.

    ReplyDelete
    Replies
    1. Can we see another JSPerf test without the delete line?

      Delete
    2. It's already there, in revisions of original test.

      Delete
  2. I still use a << 1 and a >> 1 as a shortcut for Math.floor( a * 2 ) and Math.floor( a / 2 );

    ReplyDelete
  3. Temporary variable method seems to be faster on Chrome. And V8 doesn't recognize the JS 1.7 method.

    ReplyDelete
    Replies
    1. Of course, but anyway, temp var method in Chrome is almost twice slower than bitwise swapping in Firefox. And this method works only for integers, so I don't expect everyone to use it now, I just wanted to show that it's possible.

      Delete
  4. As Anonymous above said you should verify your final results with other browsers. Especially with Chrome.

    ReplyDelete
  5. Unless only gurus are expected to read the article, you should also mention that this works mostly for integer values (except the flooring with shifting or OR).

    ReplyDelete
  6. This article shows us interesting curiosities, which meant performance improvements some years ago. And I'm sure it still means performance improvements for JS being interpreted by powerful Internet Explorer JS engines.

    Concerning this binary variable exchange:
    We can extend the integer exchange without temporary variable to all numbers (representable with the available precision) with this commonly taught short operations:

    a += b;
    b = a-b;
    a -= b;

    and this is actually slower than previous binary operations, and even more slower than temporary variable usage.

    Concerning another use case for binary operations being faster than commonly used operator: checking if an integer i is a multiple of the integer b which is a power of 2.

    The test is:

    var amount = 1e4, i, b=32;

    console.time('%');

    i = amount;
    while(i--) { i%b }

    console.timeEnd('%');

    b-=1;

    console.time('&');

    i = amount;
    while(i--) { i&c }

    console.timeEnd('&');

    And the times I get on Chrome:
    %: 37.000ms
    &: 19.000ms

    However, setting the iteration amount to 1e5 is removing this time difference. And the reason is ?

    ReplyDelete
    Replies
    1. I meant "i&b" instead of "i&c".

      Delete
  7. var arr = [1,2,3];
    ~arr.indexOf(2); // => 1
    ~arr.indexOf(4); // => 0

    one's complement in base 10 turns -1 to 0 and all other numbers to not -1

    ReplyDelete
  8. Umm...I meant -1 to 0 and all other numbers to not 0

    Therefore
    ~x will coerce to false when x === -1
    ~x and to true otherwise

    ReplyDelete
  9. In the reg2hex function, I did not get the point for doing (1 << 24) and then doing substr(1). Why is it done?
    The above code is working without these two components too (atleast for the case of #BADA55 color)

    ReplyDelete
  10. Took me time to read all the comments, but I really enjoyed the article. It proved to be Very helpful to me and I am sure to all the commenters here! Its always nice when you can not only be informed, but also entertained! Im sure you had fun writing this article.
    Microsoft dynamics training

    ReplyDelete
  11. Fantastic article ! You havemade some very astute statements and I appreciate the the effort you have put into your writing. Its clear that you know what you are writing about. I am excited to read more of your sites content.

    Latest jobs

    ReplyDelete
  12. I can see that you are are genuinely passionate about this! great information.
    thank you...!
    Hadoop training

    ReplyDelete
  13. hi...Im student from Informatics engineering nice article,
    thanks for sharing :)

    ReplyDelete