Hackerrank Solution: The Great XOR

Original Problem

Given a long integer $$n$$, count the number of values of $$k$$ satisfying the following conditions:

• $$k\oplus n > n$$
• $$0<k<n$$

where $$n$$ and $$k$$ are long integers and $$\oplus$$ is the bitwise XOR operator.

You are given $$q$$ queries, and each query is in the form of a long integer denoting $$n$$. For each query, print the total number of values of satisfying the conditions above on a new line.

For example, you are given the value $$n=5$$. Condition $$2$$ requires $$k<n$$ The following tests are run:

• $$1\oplus 5=4$$
• $$2\oplus 5=7$$
• $$3\oplus 5=6$$
• $$4\oplus 5=1$$

We find that there are $$2$$ values meeting the first condition: $$2$$ and $$3$$.

Function Description

Complete the theGreatXor function in the editor below. It should return an integer that represents the number of values satisfying the constraints.

Constraints

• $$1\leq q \leq 10^5$$
• $$1\leq n \leq 10^{10}$$

Solution

We need to count all numbers whose XOR with $$n$$ produces a greater value. The definition of the bitwise XOR is, that the resulting bit is always 1 if the bit at the same position in both variables are different. To get a feeling of how the XOR operation affects the numbers, lets have a look at the first values of $$n$$ in binary notation:

$$k$$$$n$$$$k\oplus n$$
011011

011110
101101

001100101
010100110
011100111

001101100
010101111
011101110
100101001

001110111
010110100
011110101
100110010
101110011

001111110
010111101
011111100
100111011
101111010
110111001

000110001001
001010001010
001110001011
010010001100
010110001101
011010001110
011110001111

000110011000
001010011011
001110011010
010010011101
010110011100
011010011111
011110011110
100010010001

What is astonishing, if a bit in $$n$$ at position $$m$$ is 0, it tells us that $$2^m$$ additional possible results fulfill the condition $$k\oplus n>n$$, because there are $$2^m$$ numbers that can become 1, after $$0\oplus 1$$.

That means that we only need to go through the bits of $$n$$ and if the bit at the position $$m$$ is 0, we add $$2^m$$ to the counter variable. Since we add only powers of two, we don't need to add the numbers, but can OR them together.

Furthermore, we don't calculate $$2^m$$ explicitly to save CPU cycles, but use a left-shift. Since we do this for each iteration, we shift by one bit at a time. The whole solution can then be implemented like this:

def theGreatXor(n):
m = 1
c = 0
while n > 0:
if (n & 1) == 0:
c|= m
m<<= 1
n>>= 1
return c

This algorithm runs in $$O(\log(n))$$. But when thinking about this implementation again, what we are doing actually is inverting $$n$$ within the range of the set bits of $$n$$.

So basically, it can be solved with only one $$\sim n$$ operation, with $$\sim$$ denoting binary NOT. The problem with NOT is, that it inverts all leading zeros, so we have to mask the range of the original number $$n$$ with $$2^{\lfloor\log_2(n) + 1\rfloor}-1$$. After that the solution can be shrinked to a one-liner:

def theGreatXor(n):
return ~n & (2 ** math.floor(math.log2(n) + 1) - 1)

« Back to problem overview