Bitwise JavaScript
Using Bitwise Operations in JavaScript for No Good Reason

16 December 2014

Say we have a programming problem that we’re trying to solve. We have a bag full of balls of various colours. We need to determine which colours we have an even number of and which colours we have an odd number of. We want everyone to know how smart we are, so we’ve decided to solve it using bitwise operations.

Let’s skip the part where we figure out how to read coloured balls into the computer, and just say we have an array of numbers representing the various colours. It looks something like this:

var balls = [1, 2, 1, 3, 3, 1, 2];

So we have an odd number of colour 1, and an even number of colours 2 and 3.

Solution 1: Counting

An obvious solution would be to count the number of each colour, then use the modulus operator to see if it’s even or odd.

var ballCounts = [];
for (var i=0; i<balls.length; i++) {
    var currentBallColour = balls[i];
    ballCounts[currentBallColour] = ballCounts[currentBallColour] || 0;
    ballCounts[currentBallColour]++;
}

var oddBalls = [];
for (var i=0; i<ballCounts.length; i++) {
    oddBalls[i] = ballCounts[i]%2===1;
}

for (var colour=1; colour<=3; colour++) {
    console.log('Colour ' + colour + ' is ' + 
        (oddBalls[colour] ? 'odd' : 'even'));
}

Solution 2: Tracking only even/odd state

Now let’s look at ways to simplify this. Really, we don’t need to count the number of balls, since we only need to know if they’re even or odd.

var oddBalls = [];
for (var i=0; i<balls.length; i++) {
    var currentBallColour = balls[i];
    oddBalls[currentBallColour] = oddBalls[currentBallColour] || false;
    oddBalls[currentBallColour] = !oddBalls[currentBallColour];
}

for (var colour=1; colour<=3; colour++) {
    console.log('Colour ' + colour + ' is ' + 
        (oddBalls[colour] ? 'odd' : 'even'));
}

Solution 3: Going Bitwise

Great! Now let’s pull in those bitwise operations. We’re going to make four changes to the above code.

  1. Instead of an array of booleans, we’re going to use a single number to represent our result. If colour 1 is odd, then the first digit if you represent the number in binary is a 1.
  2. Instead of using the ball colour as an array index, we need to get a single bit in the right position. We do this by taking the number 1, and using the bit shifting operator to move it the right number of positions.
  3. To swap between even and odd for a single ball, we use the bitwise exclusive or operator. The way I like to think of this operator, it takes the first operator, and for every 1 in the second operator it swaps the state of corresponding bit. In combination with the bit shifting operator, we use this to flip only the bit in the correct position.
  4. Having done this, we need a way to test a single bit. Before, this was done by just accessing the correct element in the array. We do using a bitwise and. The bitwise and operator can be thought of as a mask that you can apply to another number, leaving only bits that are 1 in both numbers. So if we shift a single bit to the right position, and it with the original number, and if the result is non-zero then that bit was 1 in the original number.

Put that all together, and this is what we get:

var oddBalls = 0;
for (var i=0; i<balls.length; i++) {
    var currentBallColour = balls[i];
    var bitmask = 1 << currentBallColour;
    oddBalls ^= 1 << balls[i];
}

for (var colour=1; colour<=3; colour++) {
    console.log('Colour ' + colour + ' is ' +
        ((oddBalls & (1 << colour)) !== 0 ? 'odd' : 'even'));
}

Pitfalls

Let’s ignore any readability issues and just look at how bitwise operators work specifically in JavaScript, and what this means for our code.

Fractions

One oddity that you might come across in bitwise operations in JavaScript is that the number is first cast to an integer. What does this mean for our problem? Well, say you have a ball that is half way between blue and green. Blue is 1 and green is 2, so in your ball array you have it captured as 1.5. In solutions 1 and 2, things will generally still work, where 1.5 is now a new colour. You’ll need to make some alterations to get the solution out in the end, but nothing will break too badly.

Using solution 3, 1 << currentBallColour will implicitly cast the result.

1 << 1; // returns 2
1 << 1.5; // also returns 2
1 << 2; // returns 4

So your blue/green ball will be interpreted as blue.

Many different colours

Normally when working with numbers in JavaScript, you don’t differentiate between integers and floating point numbers. Like with many things in JavaScript, if it looks like an integer you can treat it like an integer. If you have fractions, then it’s a floating point number. One gotcha of this is that when you have a really big number you have less precision. According to the documentation, this happens when your number is Math.pow(2,53) and higher. To give an example of this:

Math.pow(2, 53); // returns 9007199254740992
Math.pow(2, 53) + 1; // also returns 9007199254740992

If you’re using bitwise operators however, the number is first cast to a 32 bit integer. The consequence to our solution here is that if we have more than 32 ball colours, things start going wrong. Specifically, the bit shifting operator wraps bits around as you shift them, so if you’re shifting left, the bits from the far left reappear at the right. Here’s an example of how this will affect a ball with colour of 33:

1 << 1; // returns 2
1 << 33; // also returns 2

Conclusion

Bitwise operators are useful, and can be applied with great effect to problems. Just be aware of the pitfalls when using them. The strangest thing that bitwise operators do in JavaScript specifically is first cast the number to a 32 bit integer, which may lead to things working in an unintuitive way.


If you liked this article, please share it on Twitter, Facebook, Google+, or by using the Permalink.


You can send me comments on this post at justin@worthe-it.co.za, or @JWorthe.


More on Worthe It

Next Post

04 Jan 2015

Applying new experience to a language I haven't used in a long time
Latest Post

14 Aug 2017

A retrospective on a Rust audio signal processing program I wrote
Browse the Blog Archive

16 Dec 2014 - 14 Aug 2017

See all of the stuff I've written and put on this site.