HackerRank: Sum vs XOR
Every now and then one encounters a coding challenge that requires working with bitwise operators. “XOR” stands for “exclusively OR,” as opposed to simply “OR.” The difference is summarized in this table:
With XOR, having two identical bits, either two 1's or 0‘s will result in a 0. This HackerRank challenge requires understanding the difference between OR and XOR to solve the challenge.
The problem statement can be found here:
Given an integer n, you need to find how many values of x from 0 to n — 1 exist such that the sum of n + x equals n XOR x.
First of all, let’s make sure we understand what n XOR x represents (notated as n ^ x in most computer languages).
Fortunately, this problem is only asking us to count the number of values of x that will meet these conditions.
In the instance of the number 10, which is 1010, after trying all 10 possibilities, a pattern emerges that only values pairing a 1 or 0 with a 0 will work:
So there are 2 zeros in binary 10, and 2 possibilities, 0 or 1, to pair with them, for a total of 2 * 2 = 4 possibilities.
Binary 42 is 101010, which has 3 zeros in it. The valid candidates are:
There are 2 * 2 * 2 = 8 valid possibilities
The pattern that is emerging will prove to be 2 ** (zeroCount), or Math.pow(2, zeroCount) in JavaScript
So the solution to this coding challenge is fairly short. Count the number of zeros in the binary string and that number will be the power applied to a base of 2. The only thing left is how to convert an integer to its binary counterpart. The can be done in JavaScript using the .toString() method with the argument of 2 for conversion to a binary string:
And the solution:
Coding challenges involving bitwise operators rely on understanding logic tables and being aware of the specific language options that convert base 10 integers into their binary string counterparts and vice versa. With this knowledge, you should be well-equipped to tackle most of these types of problems.
Happy coding!
