Example: Non Repeating Numbers 2 - rFronteddu/general_wiki GitHub Wiki

Explanation

Given an array arr[] containing 2N+2 positive numbers, out of which 2N numbers exist in pairs whereas the other two number occur exactly once and are distinct. Find the other two numbers. Return in increasing order.

We remember that

• n^n == 0, n^0 = n, and that ^ is cumulative and associative
• If we XOR all the elements. xor = arr[0]^arr[1]^arr[2]…..arr[n-1], xor will only contain bits that are different between x and y
• We can use xor & (-xor) to isolate the rightmost set bit in xor which identify the difference between x and y.
• We can now isolate two sets
  • Elements with the same bit set at the chosen position as in xor
  • Elements with the opposite bit at the chosen position as in xor
• Since x and y differ at the chosen bit position, one will be in group 1 and the other in group 2
• Now we XOR all elements in each group, and you are left with x and y.
• We now xor x and y to remove the common part

More on

Two's Complement Representation:

• In binary, a negative number is represented using two's complement.
• The two's complement of a number is obtained by inverting all the bits (performing a bitwise NOT) and then adding 1 to the result.
• For example, if diff = 6 (which is 0110 in binary), then -diff would be the two's complement of 6, which is -6 = 1001 + 1 = 1010 in binary.

Bitwise AND with Two's Complement:

• When you perform diff & -diff, you're effectively isolating the rightmost set bit (the lowest bit that is 1) in the original number.
• This is because diff & -diff will have a single 1 bit at the position of the lowest set bit in diff, and all other bits will be 0.

Why This Is Useful:

• If x and y are two numbers, and diff = x ^ y, then diff will have 1 bits in positions where x and y differ.
• The expression diff &= -diff; will leave only the lowest set bit in diff, which corresponds to the rightmost position where x and y differ.

Code

public static int[] get2NonRepeatingNos(int[] nums) {
    int diff = 0;

    // all the duplicate items cancelled each other leaving only the xor between x and y.
    for (int num : nums) {
        diff ^= num;
    }
 

    // isolate the rightmost bit in diff, this bit will be different because x != y
    diff &= -diff;

    int x = 0;
    int y = 0;
    
    // remove the shared parts from the two groups to reconstruct the original numbers
    // the two groups are the one naturally formed when the bit is set and when it is not
    for (int num : nums) {
        if((num & diff) == 0) {
            // the bit is not set
            x ^= num;   
        } else {
            y ^= num;
        }
    }

    return x < y ? new int [2]{x, y} : new int [2]{y, x}
}