The Bitwise XOR Operator and How it Helped me “Find the odd int”

On a recent trip to CodeWars, I solved a (thankfully) straightforward algorithm called “Find the odd int.” The prompt was as follows:

Given an array, find the integer that appears an odd number of times.

There will always be only one integer that appears an odd number of times.

I had seen problems like this a few times before, and my instinct was to collect the integers as keys in an object and adjust their values to reflect the number of times they appeared. Then I could iterate through the keys of my new object until I found one with a value whose modulus 2 was 1 (meaning it couldn’t be evenly divided by 2 and was therefore an odd number). You can imagine my excitement when I actually got that to work:

Being new to Java and to algorithm problems in general, I figured there were probably a few ways to optimize my solution. Even now, I realize that I could have simplified by using a HashSet and removing values the second, fourth, sixth etc time they appeared. I was shocked, however, to find a solution as brief and simple as this one:

code courtesy of over 20 warriors on CodeWars

A lot of this is straightforward if you’re familiar with Java. We’ve got our FindOdd class and a method therein. The method is going to return an int and takes an argument that is an array of ints. Inside of the method, we assign a variable, xor, the value of 0. We then start a for loop to check every element of the argument array. Inside of the loop, we are introduced to the Bitwise XOR Operator:

xor ^= A[i];

Bitwise XOR Operator

The Bitwise XOR Operator (also known as Bitwise XOR or XOR operation) works like the other operators we may be more familiar with: +, -, *, /, >, <, =, etc. It takes values on either side of it and determines a third value based on their relationship. XOR is shorthand for eXclusive OR, meaning that we’ll return one thing if the compared values are the same, and something else if they are different.

That’s where bitwise comes in: Bitwise XOR is part of a larger subset of Bitwise operators. As we know from my previous blog (thanks loyal readers), bit is shorthand for binary digit, can have one of two values: a 0 or a 1. Bitwise operators compare two values on a bit level, converting them to binary code and then going index by index to create a new value. If this feels a little fuzzy, check out this great explanation from Envato. Alternatively, read on for some examples that might flesh out the concept.

Bitwise XOR will look at two bits and return a 0 if they are the same or a 1 if they are different. Here’s a chart of our possible outcomes from using XOR on two bits:

0 ^ 0 // => 0
0 ^ 1 // => 1
1 ^ 0 // => 1
1 ^ 1 // => 0

I would argue that, at this point, we’re no closer to solving our algorithm or understanding the provided solution. First of all, we’re dealing with an array of integers, not bits — what if the numbers aren’t 0 or 1?

Bitwise XOR will work on integers, but it will still work on a bit level. It will compare the bits at each index of the integer’s binary counterpart, building a new value that can be converted from binary to decimal notation. Here’s an example:

/* PSUEDOCODE
// convert decimal notation to binary notation:
7 ^ 10 => (0)111 ^ 1010
// we add a zero up front for the binary value of 7 so that we can compare these two by index
// Let’s build our binary value one index at a time. We’ll start from the left. The first digit of the first number is 0 and the first digit of the second number is 1. Since they are not the same, our XOR operator returns 1:
0 ^ 1 => 1
// As we move through the numbers, we build a new binary value
1 ^ 0 = 1
1 ^ 1 = 0
1 ^ 0 = 1
// So 7 ^ 10 => 0111 ^ 1010 => 1101 => 13
*/

To recap: we would expect the result of 7 ^ 10 to be 1101 because our XOR operator compares the bits of each index of our two values. 1101 converted back to decimal notation is 13. Feel free to head over to your terminal to check it out (this is not exclusive to Java, so if you’re a JS native like I am, you can give it a shot there).

We’ve got an even better understanding of the XOR Operation, but I still don’t understand how it’s useful in solving this problem. Let’s look again at the code and fill in some values:

This method should be able to accept an argument of an array of integers and return the integer that appears an odd number of times. It’s unclear as to whether this method interprets 0 or negative numbers as integers, so let’s assume that we’re working with integers greater than 0. To help explore this logic, let’s use a simple array example: [2,3,3].

Our expected output is 2, because it is the only integer that appears an odd number of times. If we ran the findIt method using [2,3,3] as an argument, xor would be set to 0 and we would enter our for loop with i set at 0. So the internal logic would be transformed from:

xor ^= A[i];

To:

xor = 0 ^ 2;

The ^= operation is comparing a value and setting a variable at the same time. In other words, xor will be assigned a value that is equal to the current value of xor ^ the current value of Array A at index i. Hence, xor = 0 (current value of xor) ^ 2 (current value of Array A ([2,3,3]) at index i (0).

Let’s run our evaluation:

00 ^ 10 => 10

10 in binary translates to 2 in decimal notation, so we set xor to 2. This makes sense — if our array ended here, we would return 2, which would be the only integer that appears an odd number of times. But the array continues, so we increment i and run the logic again:

xor = 2 ^ 3;

In binary:

10 ^ 11 => 01
xor = 1

Now this is a bit confusing because 1 isn’t a value in our array. If we returned 1, we wouldn’t be anywhere near a solution!

But we would also have an illegal input: the prompt states that only one number will appear an odd number of times. If our array ended here, both 2 and 3 would appear once. So we’ll see if adding the second 3 fixes our solution:

xor = 1 ^ 3;
01 ^ 11 => 10
10 (binary) => 2 (decimal)
xor = 2;

The loop ends and we return 2…which is the correct answer. How did that happen?? This has to be a coincidence.

Let’s check it out with a longer array and larger numbers. For the sake of simplicity, I won’t break things down to binary this time:

array = [1,4,10,4,4,10,1,10,10]
0 ^ 1 => 1
1 ^ 4 => 5
5 ^ 10 => 15
15 ^ 4 => 11
11 ^ 4 => 15
15 ^ 10 => 5
5 ^ 1 => 4
4 ^ 10 => 14
14 ^ 10 => 4

4 appeared three times, 1 appeared twice, 5 appeared 4 times. 4 was the right answer! How could this be possible?

The more complex example actually gives us a lot of helpful data for explanation. First, we can see that if any number uses the XOR operator with a 0, that number will be the result. Any index containing a 1 will return a 1 and any index containing a 0 will return a 0. So, at the very least, our variable xor will be assigned the first value in our array during the first loop.

We might also notice that the XOR operator seems to group numbers in threes. The two numbers we use for our comparison generate a third that, when compared with one of the original two, will return the other:

a ^ b => c
c ^ b => a
c ^ a => b

This is the key to this solution. After we set xor to the first integer in our array (value 1), we compare it with the next integer (value 2), generating a third value (value 3). If we come across value 1 again while traversing the array, value 3 will be transformed into value 2. If we come across value 2, value 3 will be transformed into value 1. We could layer this a thousand times but eventually, as long as only one integer appeared an odd number of times, that integer would be revealed. The integer that lacks a companion —it is the odd one out.

Conclusion

I found this solution really tricky to understand and equally difficult to explain. If the explanation is still hazy, it might be worth manually walking through your preferred IDE and trying to follow the calculations one step at a time. Even if the explanation for why this works doesn’t resonate, it’s really valuable to understand how it works. If anything, just put focus into that!