"Maximizing XOR" Challenge Sample

Introduction

The site hackerrank.com was recently brought to my attention and I thought I'd share some insight. Briefly, HackerRank is a site that hosts a wide collection of small programming challenges and which has the ability to automatically compile and run unit tests on submitted source code. The idea is that somebody creates a scenario that can be solved with a single file of source code, along with a set of tests and required results, then anybody who signs in can type in their own code and attempt to solve it. It's something like a collection of puzzles where you win if your code can successfully pass the unit tests. This article is about one of the "easy" "warm up" challenges.

Background

This is about the fourth Warmup challenge under Algorithms, entitled "Maximizing XOR". The challenge can be found at this URL: https://www.hackerrank.com/challenges/maximizing-xor (note that you may have to sign up/in).

Essentially, the challenge is to write a program that accepts two 32-bit integers from the console, then with every combination of two integers between them, it must find out the highest bitwise XOR value that can be computed from any such pair. (The problem assumes that the numbers occur from lowest to highest, but the final solution I present does not depend on the order.)

SPOILER WARNING: If you want to take this challenge yourself, you should save this article until after you are finished to avoid giving away potential solutions.

Working on the Challenge

The wording of the challenge itself leads to a simple, though inefficient solution.

"
## PSEUDOCODE

/--Function to compute MaxXor for integers (L, R) returning an integer:
|  Let M start at 0.
|/--Loop integer I from L through R by 1.
||/--Loop integer J from L through R by 1.  ## This covers some redundant combinations,
|||                                         ## but it's quick and dirty to code.
|||/--Is I XOR J greater than saved value M ?
||||--Yes: Save it as the new value of M.
||||--No:  Leave M alone and keep going.
|||\
||\
|\
|  Return the value of M and exit the function.
\

"  

If you code something like this in the language of your choice, you'll probably pass all the unit tests and get the full 20 points.

It really bothered me, though. It shouldn't be necessary to do an inefficient search to find this value as if it were a random data element or a prime number. The sample data in the challenge instructions appear to contain some kind of pattern. So, what is it?

First, look at the truth table for XOR:

eXclusive OR:
^| 1 | 0 |
-+---+---+
1| 0 | 1 |
-+---+---+
0| 1 | 0 |
-+---+---+

XOR is true only when the inputs are different, or more importantly it is false when the inputs are the same. Since we are looking through ranges of integers, only certain bits will change between any pair. Every time an integer increments, it changes the lowest order bit which eventually carries up into the higher order bits. So, let's take the endpoints of the range and see how many low order bits we have to get rid of until they are identical; we can do that by dividing each by two and comparing them at each step, thus having at most 32 steps. The nested loops we started out with could have up to (2^32)^2 or 4,611,686,018,427,387,904 iterations if the user enters full 32-bit integers, and that would take much longer than I'm willing to wait.

Anyway, I ended up with this function in C#:

static int maxXor(int l, int r)
{
    // Find out which bits actually change.
    int i = 1;
    while (l != r) { l /= 2; r /= 2; i *= 2; }
    return i - 1;
}

The left and right endpoint values are divided by two with integer truncation and compared until what's left is identical, while calculating 2^(number of iterations) at the same time, then subtracting 1 from the result giving exactly the same number as the maximum XOR in the range. The code passes all the unit tests, and what's more, it doesn't even use the XOR operator (which is ^ in C#).

Great, I won 20 points!...the same as I would have gotten with the quick-and-dirty solution. So, now I wondered if somebody else arrived at the same conclusion, which meant it was time to hit the Web search engine. Most of what I managed to find in searches just repeated the obvious nested loop solution, but I managed to locate this one on a mostly Chinese language site: http://www.mamicode.com/info-detail-183676.html.

The code appears to be written in C, and it doesn't quite work in C# because if you enter the same number for both inputs, which results in (n XOR n) which is always zero, Math.Log(0) returns -infinity and the final result ends up wrong. The easiest way to fix this is to simply return zero if the entries are duplicates, so I ended up with the following:

static int maxXorC(int l, int r)
{
    if (l == r)
        return 0;
    else
    {
        int bitLen = (int)(Math.Log(l ^ r) / Math.Log(2));
        return (2 << bitLen) - 1;
    }
}   

Why use the XOR operation just on the endpoints? Well, that gets rid of the duplicate high order bits so we only have to scan one integer instead of two. But, why use logarithms to count the number of bits? That triggers floating point operations when we're trying to calculate a small integer. Let's try combining this with my approach to come up with something more efficient.

static int maxXorJ(int l, int r)
{
    // Find out which bits actually change.
    int i = 1;
    int x = l ^ r;
    while (x > 0) { x >>= 1; i <<= 1; }
    return i - 1;
}

So the XOR operator is back, and now I'm using bit shifting to find the highest changing bit and doing the multiplication (a left bit shift on an integer value multiplies it by two). If I benchmarked this and/or looked at the IL, this would probably prove to be the most efficient version I've tried, but I've already done much more than the challenge called for or would give any credit for.

Criticisms / Conclusions

So, what did I just accomplish from all of the effort I put into this challenge? There are several problems with programming challenges like the ones on HackerRank. First, I've found a super-effective solution, but it solves a problem that probably doesn't matter to anybody. I would rather be writing software that does something arguably useful.

Second, this solution to the challenge was probably just due to an unforeseen flaw in the design of the problem. Artificial problems can be as tricky to create as they are unrewarding to solve. It's also hard to relate to an artificial problem. Was anybody really that curious about the maximum bitwise exclusive "or" between two integers? Some of the challenges are so contrived I don't even want to understand the alleged "problem" much less solve it.

Third, attempting to evaluate software development with simple and objective rules is fraught with peril. In the case of HackerRank, your results are evaluated by a machine using a handful of unit test cases, with no means of performing stress tests or efficiency tests (except that it will time out if your code loops too long), checking for readability or quality, etc. As far as I can tell, you get the same number of points for a slow, sloppy solution as for an efficient, elegant one. Worse, it's possible to submit a technically wrong solution that passes all the dozen-or-so unit tests depending on how well the tests were planned. I think by "hacker" they might mean "creator of quick and dirty solutions that meet minimal requirements". As you may guess from all of this optimization I've done, that isn't the kind of "hacker" I want to be.

I'm not saying HackerRank and similar programming challenges are not useful. Programming challenge problems are great as exercises to learn to program or to learn a new programming language. As such, I will probably use HackerRank in the future as a platform to practice some of the languages it incorporates that I don't already know. For instance, at this time I don't know enough D to write even a small application that does anything I need, but I was able to solve the first HackerRank challenge in it. I may continue solving challenges in D until I'm ready to create some useful software. Also, it doesn't prevent you from going above and beyond the requirements, so it can provide an environment to learn something new that can be shared in an article like this one.

History

• Initial publication