Xoring in constant time in Java

Question

I was inspired by this answer and the explanation and decided to support negative numbers. While testing, I noticed that the solution didn't handle the case with one number in the given range. A quick way to fix it was just adding

else if (a == b) {
    return 0;
}

Here is what I have:

package xor;

public class Xor {

    public static int getXorNeg(int x) {
        if (x > 0) {
            throw new IllegalArgumentException("x cannot be positive");
        }
        int res[] = { 0, x, 1, x - 1 };
        return res[-x % 4];
    }

    public static int getXorPos(int a) {
        if (a < 0) {
            throw new IllegalArgumentException("a cannot be negative");
        }
        int[] res = { a, 1, a + 1, 0 };
        return res[a % 4];
    }

    public static int getXor(int a, int b) {
        if (a > b) {
            throw new IllegalArgumentException("a must be less than or equals to b");
        } else if (a == b) {
            return 0;
        }
        if (b < 0) { // both a and b are negative
            return getXorNeg(a) ^ getXorNeg(b + 1);
        } else if (a > 0) { // both a and b are positive
            return getXorPos(b) ^ getXorPos(a - 1);
        } else { // a is negative, and b is positive
            return getXorNeg(a) ^ getXorPos(b);
        }
    }

    public static int getXorInLinearTime(int a, int b) {
        if (a > b) {
            throw new IllegalArgumentException("a must be less than or equals to b");
        } else if (a == b) {
            return 0;
        }
        int res = a;
        for (int i = a + 1; i <= b; i++) {
            res ^= i;
        }
        return res;
    }

}

Testing.

package xor;

import org.junit.Assert;
import org.junit.Test;

public class XorTest {

    @Test
    public void xorNegModZero() {
        int value = -84;
        int res = Xor.getXorInLinearTime(value, 0);
        Assert.assertEquals(res, Xor.getXorNeg(value));
    }

    @Test
    public void xorNegModOne() {
        int value = -145;
        int res = Xor.getXorInLinearTime(value, 0);
        Assert.assertEquals(res, Xor.getXorNeg(value));
    }

    @Test
    public void xorNegModTwo() {
        int value = -42;
        int res = Xor.getXorInLinearTime(value, 0);
        Assert.assertEquals(res, Xor.getXorNeg(value));
    }

    @Test
    public void xorNegModThree() {
        int value = -43;
        int res = Xor.getXorInLinearTime(value, 0);
        Assert.assertEquals(res, Xor.getXorNeg(value));
    }

    @Test
    public void xorPosModZero() {
        int value = 84;
        int res = Xor.getXorInLinearTime(0, value);
        Assert.assertEquals(res, Xor.getXorPos(value));
    }

    @Test
    public void xorPosModOne() {
        int value = 145;
        int res = Xor.getXorInLinearTime(0, value);
        Assert.assertEquals(res, Xor.getXorPos(value));
    }

    @Test
    public void xorPosModTwo() {
        int value = 42;
        int res = Xor.getXorInLinearTime(0, value);
        Assert.assertEquals(res, Xor.getXorPos(value));
    }

    @Test
    public void xorPosModThree() {
        int value = 47;
        int res = Xor.getXorInLinearTime(0, value);
        Assert.assertEquals(res, Xor.getXorPos(value));
    }

    @Test
    public void xorLeftAndRightPositive() {
        int from = 47;
        int to = 67;
        int res = Xor.getXorInLinearTime(from, to);
        Assert.assertEquals(res, Xor.getXor(from, to));
    }

    @Test
    public void xorLeftAndRightNegative() {
        int from = -67;
        int to = -47;
        int res = Xor.getXorInLinearTime(from, to);
        Assert.assertEquals(res, Xor.getXor(from, to));
    }

    @Test
    public void xorEquals() {
        int from = -67;
        int to = -67;
        int res = Xor.getXorInLinearTime(from, to);
        Assert.assertEquals(res, Xor.getXor(from, to));
    }

    @Test
    public void xorLeftNegativeAndRightPositive() {
        int from = -47;
        int to = 67;
        int res = Xor.getXorInLinearTime(from, to);
        Assert.assertEquals(res, Xor.getXor(from, to));
    }

    @Test(expected = IllegalArgumentException.class)
    public void xorPosWithNegative() {
        Xor.getXorPos(-1);
    }

    @Test(expected = IllegalArgumentException.class)
    public void xorNegWithPositive() {
        Xor.getXorNeg(90);
    }

    @Test(expected = IllegalArgumentException.class)
    public void xorInvalidRange() {
        Xor.getXor(10, 9);
    }
}

Answer 1

The big issue that strikes me is documentation. Looking at the code, I have very little idea of what it's supposed to do, and even less idea of whether or not it's correct.

What do a and b mean? In particular, what is the range of numbers that are xored? Without looking at getXorInLinearTime I would guess that it's from a inclusive to b exclusive, but looking at getXorInLinearTime that seems to be wrong.

What do getXorNeg and getXorPos do? They're public, so presumably they're intended to be useful quite apart from getXor, but I don't see for what.

Clever code needs good commenting. The trick used by getXor is definitely clever enough that it requires an explanation of what's going on, and really I would like to see a formal proof of correctness.

Are both getXorNeg and getXorPos required? They seem to be treated differently (both negative => getXorNeg(a) ^ getXorNeg(b + 1) but both positive => getXorPos(a - 1) ^ getXorPos(b)), suggesting that there's an out-by-one error in the implementation of one of them, and I suspect (although I haven't tested it) that getXorPos would work for negative numbers too if the % were replaced by a true modulus operation (i.e. in this special case & 3 instead of % 4).

Why is getXorInLinearTime in the public interface of the implementation class? Its only purpose would seem to be for testing the efficient getXor, so in my opinion it belongs in the test class.

---

Addendum: I think that getXorInLinearTime must be incorrect. If a < b it xors the numbers from a inclusive to b inclusive, but if a == b it xors the numbers from a inclusive to b exclusive (or some other empty set). If it's intended always to xor from a inclusive to b inclusive then a == b doesn't need a special case, and should always return a.