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:

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)