0% completed
Introduction to Bitwise XOR Pattern
XOR is a logical bitwise operator that returns 0 (false) if both bits are the same and returns 1 (true) otherwise. In other words, it only returns 1 if exactly one bit is set to 1 out of the two bits in comparison.
It is surprising to know the approaches that the XOR operator enables us to solve certain problems. For example, let’s take a look at the following problem:
Given an array of
n-1integers in the range from1ton, find the one number that is missing from the array.
Example:
Input: 1, 5, 2, 6, 4
Answer: 3
.....
.....
.....
Miguel
· 2 years ago
I think that it would be helpful to mention that XOR is involute, meaning that it is a self-inverse function. This means that we can apply xor some number of times and undo the operations by applying the XOR function again.
This is why we can effectively "XOR in" all 1->n numbers into x1 and then "XOR in" all numbers in our actual list into x2. Then when we XOR x1 by x2, we are effectively undoing all the numbers we "XOR'ed into" x2 from x1, leaving us only with the number that was never "XOR'ed into" x1 (our missing number).
ex: 0 ^ 1 = 1 ^ 2 = 3 ^ 1 = 2 ^ 2 = 0 (note that reapplying xor got us back to 0)
ex: 0 ^ 1 = 1 ^ 2 = 3 ^ 3 = 0 ^ 4 = 4 ^ 3 = 7 ^ 2 = 5 ^ 1 = 4 (note, we are left with the only number we did not XOR in twice)
Yogi Paturu
· 5 years ago
Are the C++ and JS solutions supposed to be swapped for the first algorithm?
Sonia
· 4 years ago
this gives wrong answer for missing number question on leetcode
sweetykumari
· 3 years ago
I didn't understand both for loop:
//why we are xor nums.Length+1?
//why we are xor nums.Length+1?
int x1 = 1; for (int i = 2; i <= n; i++) x1 = x1 ^ i;
////why we are xor nums.Length; isnt it should be nums.Length-1? // x2 represents XOR of all values in arr int x2 = arr[0]; for (int i = 1; i < n-1; i++) x2 = x2 ^ arr[i];