The Exclusive OR (XOR) Explained

I recently ran into a code puzzle; the question asked for the finding the unique element in a list of integers given that every integer appears twice except the single special element.

My first solution

You could use an array to hash elements to buckets (sort of like counting sort) and then flip their values every time. Something like this:

function findUniq(entries) {
    let arr = new Array(100);
    for(let i = 0, i <= entries.length ; i++){
        arr[entries[i]] = !arr[entries[i]];
    }

    for(let i = 1; i <= 100; i++) {
        if(arr[i]) {
            return i;
        }
    }
    
    return -1;
}

The array approach above would fail if you have to deal with streams as you would run out of space. As always, there are multiple ways to solve the problem; one such elegant approach can be expressed as a one-liner and runs in O(N).

let nonRepeated =
x => x.reduce((acc, cur) => acc ^ cur, 0);

nonRepeated([1,2,2,3,3,4,4,-4,-4]); // 1

The ^ is the bitwise XOR. Now let’s dive into how it works.

XOR: eXclusive OR

Xor stands for exclusive OR and it literally means that it’s an exclusive OR; its truth table is shown below:

Note that XOR is both commutative and associative. Also, for any value a, 

a ^ a; // 0
a ^ 0; // a

Applications of XOR

Most of the applications of XOR come from low-level computing and microcomputers and processors. However, this doesn’t mean some of its strengths can’t be applied to new scenarios. Here are a couple more examples.

1. Flipping bits / Toggles

As seen in the truth table above, the results of XORing a bit is the inverse of itself.

0 ^ 1; // 1
1 ^ 1; // 0

This can be leveraged with true/false which coerce to 1/0 respectively to create a toggle. Don’t do this – it is confusing.

!!(true ^ 1); // false
!!(false ^ 1); // true

2. Determining Equality

One of the fastest operations at the hardware level is the XOR. However, the way processors are built nowadays means there might be little or no performance gains when writing high-level code using these tricks – the cost of that ‘speed’ lies in the complexity and readability of code.

This knowledge may come in handy in some cases like:

• You have to write low-level code or work in environments with no support for the equality operator.
• You need to quickly find a sentinel value with strict performance limits. E.g. with bits coming over the wire over the Internet.
• You run into a codebase with such code

Do a bitwise XOR of two 32-bit values; if the result is zero, then both values are equal.

let isEqual = (a,b) => !!(a ^ b);

3. Cryptography

Assuming that c = a ^ b; then it is possible to get either a or b back by XORing c with the corresponding value.

Leveraging the earlier discussed mathematical rules of XOR, it follows that

c  => (a ^ b)

c ^ a => (a ^ b) ^ a => b ^ a ^ a => b ^ 0 => b

c ^ b => (a ^ b) ^ b => a ^ b ^ b => a ^ 0 => a

Now if you have a key a you can easily encrypt information. XOR ciphers are cheap and fast to compute but not so secure. However, when combined with one-time pads, then it gives the most secure cipher possible.

4. Hardware

XOR comes in handy at the hardware layer, especially at the chip layer. Parity and error detection are some of such applications.

For example, for even-parity bit streams, XORing every single bit should result in a 0; a non-zero result implies an error in transmission. While this may not guard against double errors, it is still better than nothing.

Another trick for low-level hardware operations (computer engineers and compiler designers) is to clear a register by XORing the contents with itself.

Conclusion

What other cool things have you used XOR for? I have heard of people using XOR to solve the trick interview question that asks you to swap the value of two integers without using temporary values or addition/subtraction.