Bitwise Operators

I recently needed to determine if the index when looping through an array was odd. I've had to do this a million times and everytime I have to look it up so I'm finally documenting it.

There are a number of ways to do this but one of the shortest ways is to make use of AND bitwise operator (&). For example:

const array = ["this", "is", "an", "example"];

array.forEach((arr, index) => {
  const isOdd = (index + 1) & 1;

  if (isOdd) {
    // ...
  }
  // ...
});

How does this work?

MDN says this about the AND bitwise operator:

The bitwise AND operator (&) returns a 1 in each bit position for which the corresponding bits of both operands are 1s.

So, it turns the number into binary (zeros and ones) and checks if the first bits are both 1, if they are then this returns truthy (1 or 0).

For example:

const one = 1; // 1 in binary
const two = 2; // 10 in binary
const three = 3; // 11 in binary

const isOdd = (number) => {
  return number & 1;
};

console.log(isOdd(1)); // returns 1 as 1 === 1 (1 in binary is 1)
console.log(isOdd(2)); // returns 0 as 0 !== 1 (2 in binary is 10)
console.log(isOdd(3)); // returns 1 as 1 === 1 (3 in binary is 11)

Odd numbers will always start with a one, whereas even numbers will always start with a zero which is why this works.

The AND bitwise operator isn't the only one, there is also OR and XOR. Let's take a look at the XOR operator

XOR Operator (^)

It took me a while to understand what the XOR operator does, so before I try to explain it lets look at some examples.

console.log(1 ^ 1); // 0
console.log(1 ^ 2); // 3
console.log(2 ^ 2); // 0
console.log(2 ^ 3); // 1
console.log(3 ^ 3); // 0
console.log(3 ^ 4); // 7

Let's look at how 1^1 returns 0.

1 in binary is 01 so we are comparing 01 and 01. The XOR operator takes the two binary numbers and it returns a new binary number where the first binary number has a 1 and the second doesn't. In the case of 01 and 01 they both match so we return 0.

Let's look at 1 ^ 2.

The number one as we know is 01 in binary and the number two is 10 so the operator returns 11 which equals three. We got 11 back from the operator as the first bit of 01 is 0, whereas, the first bit of 10 is a 1 (and the same for the second bit).

Here's a table of some numbers converted to binary so that you can do your own calculations for the others

How can this be applied?

Say you have an array of numbers and each number has a pair, except there's a problem. It turns out one of the numbers doesn't have a pair and we need to find it so we can add it. The XOR operator is perfect for this.

const pairs = [1, 1, 2, 2, 3, 4, 4]; // 3 doesn't have a pair

const singleNumber = (nums) => {
  let num = 0;
  for (let n of nums) {
    num ^= n;
  }

  return num;
};

Let's step through what this is doing line by line by adding a console.log and viewing the output.

const singleNumber = (nums) => {
  let num = 0;
  for (let n of nums) {
    num ^= n;
    console.log(`for ${n}, num equals ${num}`);
  }

  return num;
};

// => for 1, num equals 1
// => for 1, num equals 0
// => for 2, num equals 2
// => for 2, num equals 0
// => for 3, num equals 3
// => for 4, num equals 7
// => for 4, num equals 3

We can see that when a num === n then num is set to zero as the bits all line up. In the case of three however, it doesn't have a pair so it's never set to zero. When the time comes to add the bits equaling four we end up adding three and four together, in the last step we subtract that four which then returns three.