I was inspired by [this answer][1] and [the explanation][2] 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); } } [1]: https://stackoverflow.com/q/10670379/1065835 [2]: https://stackoverflow.com/a/10670524/1065835