# Xoring in constant time in Java

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);
}
}


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.

• If I use & 3 instead of a % 4 in getXorPos, it won't work for negative numbers. With positive numbers there is one pattern: 0^1^2^3 = 0, 4^5^6^7=0, and so on. With negative numbers the pattern is a different: -1^-2^-3^-4=0. As far as I understand, a &3 is the same as a % 4, but it returns a positive result when a is negative. So given a positive number a such that a % 4 == 0, the result of xoring from 0 to a (inclusive) the number itself. But given a negative number a such that a % 4 == 0, the result is 0. – Maksim Dmitriev Nov 2 '16 at 17:59
• @MaksimDmitriev, yes, now that I've tested it I see the problem. It's still relatively simple to fix: if (x < 0) x--; int[] res = { x, 1, x + 1, 0 }; return res[x & 3];. Just requires a bit more commenting to explain the if (x < 0) x--;. – Peter Taylor Nov 2 '16 at 18:59