Using Bitwise XOR to Solve the 'Lonely Integer' Problem

The Lonely Integer problem is a common coding challenge used to test your ability to count or filter numbers in an array, in order to find out which number appears only once. On HackerRank, the definition is as follows:

Given an array of integers, where all elements but one occur twice, find the unique element.

Example:
a = [1, 2, 3, 4, 3, 2, 1];

The unique element is 4.

There are multiple ways to solve this problem, including counting and filtering, or my personal favourite of utilising a Set to keep track of elements that have been seen. For example:

const set = new Set();
    
numberArray.forEach(num => set.has(num) ? set.delete(num) : set.add(num));
return Array.from(set)[0];

We are going to explore a rather different method, utilising the Bitwise XOR (^) or “exclusive-or” operator.

A Summary of Bitwise Operations

We are not going to do a deep dive into how bitwise operators work in JavaScript. If you wish to delve a bit deeper, this article will give you a good overview.

To summarise, these operators will perform comparisons of binary representations of our numbers. These operations are much quicker than their logical operator counterparts, because computers are designed to work with bits.

Bitwise XOR

Bitwise XOR is an “exlusive-or” operand, which differs slightly from OR.

Let us first look at the Bitwise OR (|) operand. MDN defines Bitwise OR as returning a number whose binary representation has a 1 in each bit position for which the corresponding bits of either or both operands are 1

const a = 6;  // Binary 0110
const b = 10; // Binary 1010

const result = a | b // 14 (Binary: 1110)

The Bitwise OR operation produces a truthy result when one or both bits are set to 1. If true, the result bit is set to 1, otherwise it is set to 0.

// Bitwise OR (|)
0 | 1 = 1   // one of the bits = 1
1 | 1 = 1   // both bits = 1
0 | 0 = 0   // neither bits = 1

0110 | 1010 = 1110

The Bitwise XOR (^) operator produces a truthy result when one bit is exclusively set to 1 and the other is exclusively set to 0. If both bits are set to 1, the result is not truthy. If true, the result bit is set to 1, otherwise it is set to 0.

const a = 6;  // Binary 0110
const b = 10; // Binary 1010

const result = a ^ b // 12 (Binary: 1100)

This is calculated as follows:

// Bitwise XOR (^)
0 ^ 1 = 1   // one bit exclusively = 1
1 ^ 1 = 0   // neither bit exlusively = 1
0 ^ 0 = 0   // neither bits exclusively = `1`

0110 ^ 1010 = 1100

Cancelling Out Numbers Using Bitwise XOR

If we take the same integer twice and perform a Bitwise XOR operation on them, they cancel each other out and return 0.

const a = 1     // Binary 1
a ^ a = 0       // 1 ^ 1 = 0 since one bit is not exclusiely set to 1

const b = 5     // Binary 101
b ^ b = 0       // 101 ^ 101 = 000 since neither corresponding bit is exclusively set to 1

Using Bitwise XOR to Solve the Lonely Integer Problem

As we just saw, an even number of identical integers compared using Bitwise XOR will cancel one another out, whereas an odd number will return the original integer. We can iterate through the integers in the array and keep the results of our comparisons in a variable using the Bitwise XOR assingment operator (^=). Let us first look at some examples of how we can calculate this by hand:

const arr1 = [1, 2, 1]  // Binary [01, 10, 01] with 2 bits for easier visualisation
01 ^ 10 = 11            // use the new binary number to compare against the next element in the array
11 ^ 01 = 10            // 2, the unique element in the array

const arr2 = [1, 2, 3, 4, 3, 2, 1]  // Binary [001, 010, 011, 100, 011, 010, 001]
001 ^ 010 = 011     // 1 ^ 2 = 3
011 ^ 011 = 000     // 3 ^ 3 = 0
000 ^ 100 = 100     // 0 ^ 4 = 4
100 ^ 011 = 111     // 4 ^ 3 = 7
111 ^ 010 = 101     // 7 ^ 2 = 5
101 ^ 001 = 100     // 5 ^ 1 = 4, the unique element in the array

By keeping a track of the resulting bits, we can perform the a Bitwise XOR comparison on this as we iterate through the array.

const array = [5, 3, 4, 1, 1, 3, 2, 4, 5]

let total = 0
array.forEach(n => total ^= n)
return total    // 2

// each iteration works as follows:
101 ^ 011 = 110     // 5 ^ 3 = 6
110 ^ 100 = 010     // 6 ^ 4 = 2
010 ^ 001 = 011     // 2 ^ 1 = 3
011 ^ 001 = 010     // 3 ^ 1 = 2
010 ^ 011 = 001     // 2 ^ 3 = 1
001 ^ 010 = 011     // 1 ^ 2 = 3
011 ^ 100 = 111     // 3 ^ 4 = 7
111 ^ 101 = 010     // 7 ^ 5 = 2, the unique element in the array