Understanding Bitwise Operations in Javascript

Bitwise operations, while uncommon in Javascript, can come in handy in a variety of scenarios. Before I lose you, here’s a quick example for a common scenario:

const isOdd(num) {
  return !!(num & 1);
}

Yup! Rather than using modulus, you can use the bitwise AND operator to determine if a number is odd or not. Not only that, this method is faster than using modulus.

From the beginning

Before we go into each bitwise operator and sample use cases, let’s think about how bits work:

Computers create numbers using either 32 bits or 64 bits. So “0” would be represented as either:

32-bit: 00000000000000000000000000000000

64-bit: 0000000000000000000000000000000000000000000000000000000000000000

Javascript, by the way, converts all your numbers to 32-bit whenever it does a bitwise operation and then turns it back to 64-bit, so for the rest of examples, we’ll be using 32-bit.

Each bit can be either a 0 or a 1. To represent the number 1, we just flip the rightmost number from 0 to 1, becoming:

00000000000000000000000000000001

To represent 2, we flip the second bit to the right:

00000000000000000000000000000010

In fact, the value of each bit is the previous bit times 2. So 8 would be:

00000000000000000000000000001000

So what’s the biggest number we can represent? It is actually 2³¹-1. First off, the leftmost bit is reserved for representing the sign (-/+). Second, why -1 ? Go into your calculator and see for yourself. Here’s how I did it:

1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 + 1024 + 2048 + 4096 + 8192 + (8192 * 2) + (8192 * 4) + (8192 * 8) + (8192 * 16) + (8192 * 32) + (8192 * 64) + (8192 * 128) + (8192 * 256) + (8192 * 512) + (8192 * 1024) + (8192 * 2048) + (8192 * 4096) + (8192 * 8192) + ((8192 * 8192) * 2) + ((8192 * 8192) * 4) + ((8192 * 8192) * 8) + ((8192 * 8192) * 16)

You can also prove it at a smaller scale by asking, what is the biggest number you can represent in a 1-bit number? 2¹ is 2 but the biggest number is really 1, so 2¹-1.

Each bitwise operator

Now that we’ve cleared up the game field, let’s look at each available operator:

Bitwise AND: &

To help myself understand this operator, I like to view it as a two-step process:

1. Do both numbers share at least one 1-bit? So 5 & 3 do because 5 is 101 and 3 is 011. Meanwhile, 4 & 3 do not (100 & 011). If no 1-bit is shared, the return value is 0.
2. What is the value for the result when you just take the shared 1-bits. 5 & 3 again only share a 1-bit at the rightmost spot, so the value is 1.

Bitwise OR: |

For this operator, I like to imagine a new empty 32-bit number and then just go through each number and put a 1 at each bit where the given number has a 1-bit. So take 4 | 3:

We start off: 00000000000000000000000000000000

Then we place the 1’s from the number 4: 00000000000000000000000000000100

And then place the 1's from the number 3:

00000000000000000000000000000111

The result is 7!

Bitwise XOR: ^

For this operator, I once again start off with a new empty 32-bit number. I place all the 1’s from the first number. For the second number, however, if I need to place a 1 where a 1 has already been placed, I have to flip it back to 0. The X, I believe, is short for Exclusive, so Exclusive OR. Let’s do 5 & 3:

We start off: 00000000000000000000000000000000

We place the 1’s from the number 5: 00000000000000000000000000000101

We place the 1's from the number 3, and convert the rightmost 1 to 0 because 3 also has a 1 at that position: 00000000000000000000000000000110

So the result is 6!

Bitwise NOT: ~

To understand how this operator works, we need to first dive into how negative numbers work in binary.

Look at this function that converts a decimal into binary:

/**
 * @param {number} n
 */
decimal_to_binary = function(n) {
  if (n < 0) {
    n = 0xFFFFFFFF + n + 1;
  }
  return n.toString(2);
}

Up until now, we’ve just been dealing with positive numbers, so we could skip over that n < 0 portion. First off, 0xFFFFFFFF is a way of representing 2³² — 1. By doing 2³² rather than 2³¹, we have flipped the sign to negative (-). This looks like:

11111111111111111111111111111111

The smallest negative number (-1) is represented with all 32 bits being equal to 1.

Consequently, -2 is:

11111111111111111111111111111110

and -3 is:

11111111111111111111111111111101

At first this seems counterintuitive, but

1. Remember that 0 can’t be negative, so it’s more efficient to have

11111111111111111111111111111111

represent the smallest negative number (-1) rather than 0.

2. At this point, we are actually doing the same procedure for generating positive numbers except:

i. we add 1 due to 1111111… being equal to -1 rather than 0, and we flip 1’s to 0’s rather than 0’s to 1’s. Let’s take -6. If we add 1, that’s -5. If that were positive that would be:

00000000000000000000000000000101

If we flip that, that becomes

11111111111111111111111111111010

Double-check that this is the case with our handy function above.

Going back to the bitwise NOT operator, what we’re doing is simply flipping all 0’s to 1’s and all 1’s to 0’s. ~-6 is equal to 5 because, as we now can visualize, we flipped the rightmost bit from 1 to 0, making it positive, and the 0’s turn into 1’s, resulting in:

00000000000000000000000000000101

Zero Fill Bitwise Left Shift: <<

This operator shifts each bit to the left n times. It is called “Zero Fill” because we fill n bits on the right with 0’s. So 5 << 2 means going from

00000000000000000000000000000101

to

00000000000000000000000000010100

which is equal to 20. Note: The 2 leftmost bits from the original binary representation of 5 are discarded as we are still representing the number with 32 bits rather than 34 (32 + 2).

Zero Fill Bitwise Right Shift: >>>

This operator shifts each bit to the right n times, and n bits on the left are filled with 0's. 2 >>> 2 becomes 0 because the two rightmost bits from the original binary representation of 2 are discarded.

Sign Preserving Bitwise Right Shift: >>

This operator shifts each to the right n times, and n bits on the left take on the values they had before the shift. This is titled “Sign Preserving” because the sign is preserved rather than being flipped to a 0 as in a Zero Fill Bitwise Right Shift. -5 >> 2 means going from

11111111111111111111111111111011

to

11111111111111111111111111111110

which is -2.

Examples

Now that we have seen the bitwise operators available in Javascript, let’s look at some uses:

/*
 * @param {number} decimal
 * @returns {string} 
 */
function decimal2binary(decimal){
  return (decimal >>> 0).toString(2);
}

While positive numbers can always be converted to binary using .toString(2), and a positive number >>> 0 has no effect other than returning that same value as no bits shifted, when you run a negative number through >>> 0, while no bits are shifted, the number is automatically converted to its binary representation. Consequently:

(-1 >>> 0) === 0xFFFFFFFF

A more real example

Alright, that last example is more of a party trick than something practical. However, let’s say you had the task to find all the subsets you could generate from an array.

So if your array is [1,2,3]

It should generate: [1], [1,2], [1,3], [1,2,3], etc.

Take a look at this solution:

function subsets(array) {
  const result = [];
  result.push([]);

  for (let i = 1; i < (1 << array.length); i++) {
    const subset = [];
    for (let j = 0; j < array.length; j++) {
      if (i & (1 << j)) {
        subset.push(array[j]);
      }
    }
    result.push(subset);
  }

  return result;
}

There’s a bitwise AND and a Zero Fill Bitwise Left Shift! Let’s delve into those:

1 << array.length: Shifting 1 to the left three times creates “1000” which is equal to 8. If you stop and imagine an array of length 2, 1 << 2 === 4. Another one: 1 << 4 === 16. What’s going on here? The number of possible subsets for an array of length n is 2^n. Since each bit is equal to 2^something, we can take advantage of those overlapping properties for an elegant solution. One final way of looking at this is 1 << array.length is also equal to:

Math.pow(2, array.length)

This second bit is more thorny:

i & (1 << j)

Provided an input [1,2,3], when the function first runs and i = 1 and j = 0, this essentially becomes i & 1 which is the same function from the beginning of the tutorial to determine odd numbers! So at the end of the loop where j = 0, we have:

[
  [],    [ 1 ], [],
  [ 1 ], [],    [ 1 ],
  [],    [ 1 ]
]

Now when j = 1, we are checking i & 2. Indexes 2, 3, 6, and 7 all match because they have a 1-bit one from the right. After this second run we now have:

[
  [],    [ 1 ],
  [ 2 ], [ 1, 2 ],
  [],    [ 1 ],
  [ 2 ], [ 1, 2 ]
]

A third and final run with j = 2 ends up:

[
  [],       [ 1 ],
  [ 2 ],    [ 1, 2 ],
  [ 3 ],    [ 1, 3 ],
  [ 2, 3 ], [ 1, 2, 3 ]
]

Unrelated PSA: Looking for a new high paying software development job? Send me your resume to alexleondeveloper@gmail.com and I’ll get back to you!

Conclusion

As you can see, we can make use of bitwise operations to create an elegant solution for subsets and other scenarios. While use cases for bitwise operations are certainly rare, it is always a good tool to keep in your toolkit! Thanks for reading and catch you later.