XOR bitwise operator a nice use case -third week running at Hacking School full-stack bootcamp
Writing this post about bitwise XOR operator while I was solving a challenge or “Kata” as they call each challenge at CodeWars (the great site for coding challenges and getting a global peer rank) after our session today at The Hacking School’s full-stack bootcamp.
Lets refer to the problem (the below gist) along with my solution first.
Note on the above code — creates the associative array object ‘count’ that will have a key-value pair for each unique element in the array, where the key is the unique element, and the value is the no of times (count) it appears. Then iterating over the array, for each element in the array, I am either incrementing the value or creating the key value pair (the value of the non-existent key evaluates to “undefined” so the || ‘or’ operator takes a zero instead, and adds the 1).
That is, for the first occurrence of a key (which is an element of the passed-in array), count[i] is set to (0 + 1) i.e. 1 — then for the second occurrence of the same element the count[i] is set to 2 and so on..
Note, from official doc, forEach() executes the provided callback once for each element present in the array in ascending order. forEach() executes the callback function once for each array element; unlike map() or reduce() it always returns the value undefined
And then, after submitting my solution, CodeWars showed me the most efficient solution (submitted by somebody else) of the same above problem, which is below.
While generally its true that, code golfing, which is essentially performing a task in as few characters as possible, is not always the best solution for production environment, as other things like maintainability, human-readibility etc are very important as well. But in this case, the one liner solution by making use of the bitwise XOR (exclusive OR) operator was way better than mine.
Explanation of bitwise XOR operator
The Mozilla official doc defines the bitwise XOR operator as — “Performs the XOR operation on each pair of bits. a XOR b yields 1 if a and b are different. Returns a one in each bit position for which the corresponding bits of either but not both operands are ones.”
Another way to look at it, XOR is a boolean operator, like && and ||, but with the following logic:
It is successful if the expression on either side is true (i.e. resulting in 1 ) (like x || y), but false (i.e. resulting in 0 ) if both sides are true (like !( x && y )).
So, if I try to represent the above in equation format, the XOR operator would work like this (the result is true if exactly one of the operands is true):
a ^ b === (a && !b) || (!a && b)
In the above, one boolean operation (0 is false, 1 is true) per bit of each number is performed.
Explanation of the above solution using XOR operator
So in this case here, in the one liner solution above, the bitwise XOR operator (“^”) cancels out (i.e. results in 0) every number once it occurs twice. So, e.g. when a number occurs once, its not candled, but if it occurs twice, it get cancelled-out. Then if it occurs a 3rd time, that 3rd time occurrence does not get cancelled but on 4th time occurrence, it gets cancelled. And the process continues — leaving the final odd number occurrence.
In another words, a^a is equal to 0 for any a, all of the matching pairs of integers will cancel each other out, leaving 0. That is then XOR’ed with the final left-over element in the array. Since 0^a is equal to a for any a, the result will be that final left-over number. Like so,
1 ^ 1 = 0
0 ^ 2 = 2
2 ^ 2 = 0
0 ^ 3 = 3
3 ^ 3 = 0
0 ^ 4 = 4
XOR is both commutative ( e.g. a × b = b × a.) and associative (i.e. ( a × b ) × c = a × ( b × c ) ), and also the identities X ^ X == 0 and X ^ 0 = X holds true. So, I can rearrange a sequence like: a ^ b ^ c ^ b ^ d ^ d ^ a any way I want, just like addition or multiplication. Because of this associative and commutative properties of XOR it does not matter in what fashion elements appear in array, we still get the answer.
So I might do: a ^ a ^ b ^ b ^ c ^ d ^ d. Since any two pairs become 0, this simplifies to 0 ^ 0 ^ c ^ 0, which is simply c.
So, for exmaple, if the given array is [3,4,1,1,2,2,3,5,5] — 3 ^ 4 is … some number, and then that resultant number ^ 1 is some other number, and then I XOR that with 1, and none of that matters because then I undo the 1, and then I throw in another intermediate result with the 2 and undo it right away, and then I undo the 3 and the 5, so I am back to the final left-over number just the 4.
So, here in this example, by simply repeatedly using XOR on all the elements of the array, any duplicates naturally filter themselves out and finally I am left with the one non-repeated integer.
The solution is great for performance, being super fast. The code go through the array list just once, and the only additional memory I need is a single value. Whereas under ``forEach()``, I am creating an an extra ``count`` object and then the additional processing loops over tht ``count`` object.
With a quick script below I tested the execution time difference (in
milliseconds) between my code and the one with the XOR operation. And the one liner code got executed around 44–53 ms earlier.
Now if 44 millisecond sounds too insignificant you should read about (from a 2008 study, which probably is even more relevant today than ever) how Amazon found every 100 ms of latency cost them 1% in sales and Google found an extra .5 seconds in search page generation time dropped traffic by 20%. There’s a huge cost of latency.
However, to remember here, this methodology only really works if one and only one unique value is appearing an odd number of times.
Lets look at a rather another and more simpler use case of ``XOR`` operator for swapping 2 given numbers with each other.
Explanation of swapNumberXOR()
A> XOR converts their operands to 32-bit integers (i.e. zeroes and ones), then perform their operations on such binary representations.
B> So in the above example > 2 and 4 in binary representation are 10 (which is same as 010) and 100 respectively. So a ^ b means 010 ^ 100 ie. ( 0 ^ 1 ) for first position then ( 1 ^ 0 ) for second position and ( 0 ^ 0 ) for the third position. Which gives “1 1 0” . So with the line of code a ^= b , I am assigning a’s value to be “100” which is the decimal 6.
C> Then With the next line ( b^= a ) means 6 ^ 4 i.e. ( 110 ^ 100 ) giving me 010 which is 2
And then finally with (a ^= b ) means 6 ^ 2 ie. ( 110 ^ 010) giving me 100 which 4.