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)