Bitwise JavaScript

Justin Wernick <>
Curly Tail, Curly Braces
2014-12-16

Abstract

In this article, I use a programming puzzle about counting coloured balls to talk about the bitwise operations, and some of the peculiar ways that they behave in JavaScript.

The Problem

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 ^= bitmask;
}

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'd like to share this article on social media, please use this link: https://www.worthe-it.co.za/blog/2014-12-16-bitwise-javascript.html

Copy link to clipboard

Tags: blog, javascript


Support

If you get value from these blog articles, consider supporting me on Patreon. Support via Patreon helps to cover hosting, buying computer stuff, and will allow me to spend more time writing articles and open source software.


Related Articles

Implementing a Bitwise Simulation

This is part three in a three part series where I discuss how I did performance optimization on a Rust applilcation I developed: a submission to a programming competition called the Entelect Challenge. In this article, I introduce the various bitwise operations, and demonstrate how I composed them together to implement all of the game rules.

Rust Iterators

In my opinion, iterators are one of the most powerful tools you can add to your toolbelt as a programmer. I've met many programmers who struggled to understand the various iterator functions and how to use them. In this article, I explore a number of iterator functions available in Rust's standard library, and explain them by giving an example of how you would get the same effect using for loops.