Repeating number problem - 2

Given an array in which all numbers except two are repeated once. (i.e. we have 2n+2 numbers and n numbers are occurring twice and remaining two have occurred once). Find those two numbers in the most efficient way.

Method 1: Use xor operators only to find the two non duplicate numbers. Xor all (2n+2) numbers first, then the n duplicate numbers are cancelled out, leaving the two unique number being XORed. The set bits in the result indicate bits at which the two numbers differ. The bit in a specific position can be either set or clear. Correspondingly, we can divide the numbers into set group numbers and clear group numbers w.r.t the set/diff bits in the result. Since all the other numbers repeat once, it doesn't change the XORed result either in the set group or the clear group. Thus, the XOR of set group and clear group are the two numbers occurred only once.
To divide numbers into set and clear group, we need to extract the set/diff bit of all 2n+2 numbers, here is the way to extract the right most diff/set bit of the XOR result of all 2n+2 numbers.

int diffBitMask = xor & ~(xor-1);

xor-1 zero the right most set bit and keep the other set bits. The complement operator ~ mask off the other set bits and set the right most one.

The code is as follows:

public class Main {
    public static void main(String args[]) {
        int arr[] = {1, 2, 6, 1, 6, 8, 7, 8};
        findNonDuplicate(arr);
    }
    public static void findNonDuplicate(int arr[]) {
        int xor = 0, xor1 = 0, xor2 = 0;
        // Xors of the all numbers, obtaining the difference mask of two numbers
        for(int i = 0; i < arr.length; i++) {
            xor ^= arr[i];
        }
        int diffBitMask = xor & ~(xor-1);   // Right most set/diff bit
        // Grouping based on the diff bit
        for(int i = 0; i < arr.length; i++) {
            if((arr[i] & diffBitMask) > 0) {
                xor1 ^= arr[i];
            } else {
                xor2 ^= arr[i];
            }
        }
        System.out.println("The two numbers that occur once are: " + xor1 + ", " 
                + xor2);
    }
}   

Output is:

The two numbers that occur once are: 7, 2