XOR (Exclusive-OR) is a special case of OR. OR could be logically ambiguous in certain scenarios where XOR specifically represents either-or v/s OR which represents both either-or and both.
Thus, with XOR, the bit is only set when one of the bits is 1, but not both. Thus,
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR of a number with itself returns 0.
1 ^ 1 = 0
29 ^ 29 = 0
Returns the same number.
1 ^ 0 = 1
31 ^ 0 = 31
(a ^ b) ^ c = a ^ (b ^ c)
a ^ b = b ^ a
Example:
Input: [1, 5, 2, 6, 4]
Answer: 3
Implementation: FindMissingNumber
When we XOR all numbers till n, it will have a certain set of set bits.
1 XOR 10 = 11
11 XOR 11 = 0
0 XOR 100 = 100
100 XOR 101 = 1
1 XOR 110 = 111
When we XOR all numbers of the array with a missing number, it will have a different set of set bits because the bits contributed by the missing number wont be there.
1 XOR 1 = 100
100 XOR 10 = 110
110 XOR 11 = 0
0 XOR 100 = 100
Doing a XOR between these two will give that missing set of bits (111 ^ 100 = 11) and hence the number. Very similar to if we summed both the arrays and found the difference.
O(n)
O(1)
Example 1:
Input: 1, 4, 2, 1, 3, 2, 3
Output: 4
Example 2:
Input: 7, 9, 7
Output: 9
Implementation: SingleNumber
Since, every number appears twice except one number, if we XOR all numbers, the numbers appearing twice will give a XOR of 0 and only the number that doesn't have a duplicate, will be left.
O(n)
O(1)
Example 1:
Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]
Output: [4, 6]
Example 2:
Input: [2, 1, 3, 2]
Output: [1, 3]
Implementation: TwoSingleNumbers
Say the two numbers we are trying to find are n1 and n2.
If we take the XOR of all elements in the array, we will be left with the XOR of the two numbers (say n3) as all other numbers with their duplicates would cancel each other out.
Now n3 will basically only have the bits set where either that bit is set in n1 or its set in n2 but not both.
So lets pick any set bit.
Now we can differentiate the elements of the array into two different groups:
If we XOR these two groups amongst themselves, all duplicates would cancel out and give the two numbers.
O(n)
O(1)
Example 1:
Input: 8
Output: 7
Explanation: 8 is 1000 in binary, its complement is 0111 in binary, which is 7 in base-10.
Example 2:
Input: 10
Output: 5
Explanation: 10 is 1010 in binary, its complement is 0101 in binary, which is 5 in base-10.
Implementation: ComplementOfBase10
From the above-mentioned first property, we can conclude that XOR of a number with its complement will result in a number that has all of its bits set to 1. For example, the binary complement of “101” is “010”; and if we take XOR of these two numbers, we will get a number with all bits set to 1, i.e., 101 ^ 010 = 111
We can write this fact in the following equation:
number ^ complement = all_bits_set
Let’s add ‘number’ on both sides:
number ^ number ^ complement = number ^ all_bits_set
From the above-mentioned second property:
0 ^ complement = number ^ all_bits_set
From the above-mentioned third property:
complement = number ^ all_bits_set
We can use the above fact to find the complement of any number.
How do we calculate ‘all_bits_set’?
One way to calculate all_bits_set will be to first count the bits required to store the given number. We can then use the fact that for a number which is a complete power of ‘2’ i.e., it can be written as pow(2, n), if we subtract ‘1’ from such a number, we get a number which has ‘n’ least significant bits set to ‘1’. For example, ‘4’ which is a complete power of ‘2’, and ‘3’ (which is one less than 4) has a binary representation of ‘11’ i.e., it has ‘2’ least significant bits set to ‘1’.
O(n)
O(1)