XOR, bitwise XOR and using it to solve an algorithm challenge
Tags: typescript, tutorial, javascript
Published: 2020-06-19 14:09:33

XOR is an interesting logical operator that is usually not used that often, but when you really need it, it comes in pretty handy.
While not directly a dedicated operator for logical operations (like && and ||), it is present as a bitwise operator in most programming languages, nowadays (especially those that derive from C in one way or the other).
This includes JavaScript and thus also TypeScript.

# XOR
This is the truth table for XOR:

| a     | b     | a XOR b |
| :---: | :---: | :-----: |  
| 0 | 0	| 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

As you can see, XOR only resolves to 1 (or true) if and only if only one of the bits (or booleans) compared is 1 (true).
In all other cases, 0 (or false) is the result.

# Bitwise XOR
XOR can also be used for a bitwise comparison like this:
```TypeScript
const result = 10 ^ 20;
// result is 30
```
As you can see, the operator used is `^`.

## How exactly does it work?
When you compare two numbers in JavaScript bitwise, the numbers are basically converted to 32-Bit integers, and then their bits are compared pair-wise (floating point numbers loose their decimal places, such that bitwise XOR does only make sense when comparing integers. Numbers with more than 32 bits have their most significant bits removed).

The number 100, for example, in binary is:
`0000000001100100`

You can read more about it [here](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators)

## An Example For Bitwise XOR
Let's say you do the following operation: `1 ^ 2`.

Then this is what is happening:
`1` is represented as `01` in binary.
`2` is represented as `10` in binary.
(omitting the leading zeros for readability)

And the following comparison is made:
`01 ^ 10`

Written among each other:
`01`
`10`

And now the following pairwise comparison is made, from right to left, above compared with below:
First position: `1 ^ 0 = 1`
Second position: `0 ^ 1 = 1`

This leads to the reconstructed result: `11` which equals decimal `3`.

# An Algorithm Challenge
There is a challenge that is present on some sites for competitive coding, coding challenges, and such.

It goes as follows:
```
Given is an array of variable length, filled with integers.
The array consists of an even number of duplicate integers and a single integer. 
The position of the lone number within the array is random.
Write a function that returns the number that has no duplicate in the array.

You may assume that only arrays which have the structure and values described
above or are present within the examples are passed to your function.

Examples:
[1, 3, 1] -> returns 3
[1, 2, 1, 3, 2, 3, 5, 4, 5] -> returns 4
[1] -> returns 1
[] -> returns null
null -> returns null
```

## How Can XOR Help Here?
Do you still remember how the bitwise XOR comparison worked?

Let's do another example and calculate `10 ^ 10`.

`10` is represented as `1010` in binary.
Thus leading to the comparison `1010 ^ 1010`.

Written among each other:
`1010`
`1010`

This leads to the following pairwise comparisons (from right to left, above compared with below):
`0 ^ 0 = 0`
`1 ^ 1 = 0`
`0 ^ 0 = 0`
`1 ^ 1 = 0`

And the result is `0000` which is just a decimal `0`.

That seems interesting, doesn't it?
We could now try to do `1 ^ 1` or `11 ^ 11` or `100 ^ 100`, the result would always be `0`.
So, an integer compared with XOR to itself leads to a result of `0`.

## Another Example
Let's compare `0` to `5`:

Which is: `0 ^ 5`.

`0` is represented as `000`
`5` is represented as `101`

This leads to:
`000 ^ 101`

Written among each other:
`000`
`101`

This leads to the following pairwise comparisons (from right to left, above compared with below):
`0 ^ 1 = 1`
`0 ^ 0 = 0`
`0 ^ 1 = 1`

And the result is `101`, which is decimal `5`.

Well, that seems interesting again.
We could, once again, try a few other comparisons, but the result would always be the number other than `0` or better said: `0 XOR any number other than zero` always results in the number other than zero being returned.

## Applying Our New Knowledge
Let's try to use our new knowledge to solve the challenge from above, by taking the first example from the challenge, and doing it manually.

First, let's write down what we know, until now:
- An integer XOR itself results in `0`
- An integer XOR `0` results in the integer itself

Let's just try XORing all numbers within the array and take a look at the result we get:

The array from the example is: `[1, 3, 1]`.

What we want to calculate is: `1 ^ 3 ^ 1`.

All numbers converted to binary:
`1` is represented as `01` in binary.
`3` is represented as `11` in binary.

This leads to the following calculation `01 ^ 11 ^ 01`.

And the individual calculations are:
`01 ^ 11 = 10`
`10 ^ 01 = 11`

Our result is binary `11` which is decimal `3`, which is exactly the number we wanted!

So, the positions of the numbers within the array are irrelevant. It doesn't matter whether the array is sorted. This means that whatever our solution looks, we don't have to worry whether the array we receive is sorted or not.

## One Last Thing Before We Code
We can even extend what we just found out.
As long as all numbers, except one, are present an even number of times, and one number is present an odd number of times, we can find the number that is present odd times with this solution.

## The Solution
With all that knowledge, you now know enough to implement a solution.
Let's use TypeScript here (just remove the type declarations and you have valid JavaScript) and get straight to the solution:

```TypeScript
function findNumberPresentOddTimes(arr?: number[]): number | null {
  // == null checks for null and undefined!
  // when our array is empty, we return null as requested
  if (arr == null || arr.length === 0) {
    return null;
  }
  let result = arr[0];
  for (let i = 1; i < arr.length; i++) {
    result = result ^ arr[i];
  }
  return result;
}
```

# That's It
Thank you very much for reading this post and I hope you learned something along the way.
There are many more concepts and techniques you can use in a clever way to solve algorithmic problems.
Just stay curious and try to understand concepts, techniques and how they all work, so you have all the knowledge to decide whether a concept or technique is applicable to a problem.

If you liked this post, consider giving me a visit on [Twitter](https://twitter.com/oliverjumpertz) where I post micro content and other interesting stuff, next to the usual joking, and sometimes memes.