Bitwise XOR operator to find missing unique ID

Question

I have an array with positive integers. All except one element in this array doesn't have a duplicate. The way to find the unique element is by using the XOR bitwise operator which returns 1 only if one of the element is 1 and false otherwise.

Following is the code:

public class Bitter {

    public static void main(String[] args) {
        int[] deliveryIds = {34, 40, 2, 21, 50, 40, 34, 2, 50};
        System.out.println(new Bitter().findUniqueDeliveryId(deliveryIds));
    }

    public int findUniqueDeliveryId(int[] deliveryIds) {
        int uniqueDeliveryId = 0;

        for(int i = 0; i < deliveryIds.length; i++) {
            uniqueDeliveryId ^= deliveryIds[i];
        }

        return uniqueDeliveryId;
    }

}

In the loop, each of the integers in the array are XORed with uniqueId starting at 0. Then, 0 is XOR'ed with 34. The result is then XOR'ed with the next integer in the array 40 and we go through the entire array.

I'm still unable to understand even after setting breakpoints and going through the entire flow one line at a time, how XORing with uniqueId (starting with it's value 0) can help us find the non-duplicate integer in the array?

Shouldn't a number like 40 XOR'ed with itself (resulting in the value 0), to confirm that it's a duplicate. Unlike here, where we are XOR'ing 0 with the first integer in the array, and the result with the subsequent number in the array. What am I missing/

Answer 1

XORing n numbers is like counting the number of 1 bits in each position, and setting the corresponding output bit to 1 if the count is odd. The order in which you are XORing them doesn't matter.

If an array contains x pairs of equal numbers and one unique number, the bits of the equal pairs cancel each other (since they contribute an even number of 1s in each position), leaving you with just the bits of the unique number.

For example, take the following list of numbers :

100100101
010110110
101101100 // the unique number
100100101
010110110

Count the number of 1s in each position:

321521522

Result of XOR (1 bit in for each odd count) :

101101100 

which is the single unique number in the list.

Answer 2

Looking at it like math, rather than code; and using ^ to mean bit-level xor, we can say that

• xor is commutative: A ^ B = B ^ A
• xor is associative: (A ^ B) ^ C = A ^ (B ^ C)
• xoring with zero does nothing: A ^ 0 = A
• xoring something twice removes it: A ^ A = 0

The first two properties imply that any reordering of a sequence of xors will yield the exact same result.

Therefore, given a sequence that contains duplicates, they will all be removed via xor:

   A ^ B ^ X ^ A ^ B  =  A^A ^ B^B ^ X  =  0 ^ 0 ^ X   =  X
                      \ reorder         \ xoring twice \ removing zeroes

Note that this trick only works if there is a single element that is not duplicate. If there were several, the result would be the XOR of all non-evenly-duplicated elements:

   A ^ B ^ C ^ A  =  A^A ^ B ^ C  =  B ^ C