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:
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
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
0results 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:
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 where I post micro content and other interesting stuff, next to the usual joking, and sometimes memes.
Top comments (0)