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, with the goal of isolating the number which 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.

In summary, these operators compare binary representations of numbers, offering faster performance compared to their logical counterparts since computers are optimised for bitwise operations.

Bitwise XOR

The Bitwise XOR is an "exclusive-or" operator, which has subtle differences compared to the Bitwise OR operator.

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 bit 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 none of the corresponding bits are exclusively set to 1

Using Bitwise XOR to Solve the Lonely Integer Problem

As demonstrated earlier, when an even number of identical integers is compared using Bitwise XOR, the result nullifies them, while an odd number of the same integer will yield 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's begin by examining some manual calculations for this process:

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 maintaining a record of the resulting bits, we can conduct Bitwise XOR comparisons on them while iterating through the array.

const array = [5, 3, 4, 1, 1, 3, 2, 4, 5]
// Binary [101, 011, 100, 001, 001, 011, 010, 100, 101]

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

Conclusion

In conclusion, the Bitwise XOR operator proves invaluable in singling out the unique integer within an array, capitalising on the even occurrence of other integers that effectively cancel each other through bitwise exclusive-OR comparisons. This approach can be flexibly extended to address various scenarios, including the identification of odd or even occurrences within an array.