Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link

I was inspired by this answerthis answer and the explanationthe 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

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

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

The package statement is part of the code
Source Link
Peter Taylor
  • 24.2k
  • 1
  • 48
  • 93

package xor;

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

}

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

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

}
Source Link
Maksim Dmitriev
  • 1.4k
  • 2
  • 15
  • 29

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