Important properties of XOR to remember

Following are some important properties of XOR to remember:

• Taking XOR of a number with itself returns 0, e.g.,
  • 1 ^ 1 = 0
  • 29 ^ 29 = 0
• Taking XOR of a number with 0 returns the same number, e.g.,
  • 1 ^ 0 = 1
  • 31 ^ 0 = 31
• XOR is Associative & Commutative, which means:
  • (a ^ b) ^ c = a ^ (b ^ c)
  • a ^ b = b ^ a

Use cases

Single Number

If we xor number to itself we get zero. So we end up with single number.

public int findSingleNumber(int[] arr) {
    int xor = arr[0];
    for (int i = 1; i < arr.length; i++) {
        xor ^= arr[i];
    }
    return xor;
}

Two Single Numbers

Tricky case. We assume that n1 and n2 have one bit difference between them.

So we do xor and find xored number. Taking rightmostSetBit.

Then we can partition numbers if the bit is set or not and find both.

public static int[] findSingleNumbers(int[] nums) {
    // get the XOR of the all the numbers
    int n1xn2 = 0;
    for (int num : nums) {
      n1xn2 ^= num;
    }

    // get the rightmost bit that is '1'
    int rightmostSetBit = 1;
    while ((rightmostSetBit & n1xn2) == 0) {
      rightmostSetBit = rightmostSetBit << 1;
    }
    int num1 = 0, num2 = 0;
    for (int num : nums) {
      if ((num & rightmostSetBit) != 0) // the bit is set
        num1 ^= num;
      else // the bit is not set
        num2 ^= num;
    }
    return new int[] { num1, num2 };
  }

Complement of Base 10 Number

XOR of a number with its complement will result in a number that has all of its bits set to 1!

We calculate bitCount by moving bit right n >> 1.

All bits set value is 2^N - 1, cause 2^N wil give us smth like 10000.... and - 1 → 11111

Then just do XOR to all bits set.