编码 - 在 java 中查找一系列数字的按位 XOR

Question

查找一个按位 XOR 作为范围，例如 (5,8( --> 5 位异或 6 | 7 位异或 8 3 位异或 15 12 预期最坏时间 复杂度 - O(log(n(( 预期最差空间 复杂度 - O(1(

我已经编写了下面的代码，你能帮我改进它吗？

static List<Integer> list;
public static void main(String[] args) {
int bitXORProduct = solution(5,8);
System.out.println(bitXORProduct);
}
public static int solution(int M, int N) {
if (isValidatedInput(M, N)) {
int lastXOR = M;
int currentXOR = 0;
try {
for (int i = M; i < N; i++) {
currentXOR = computeXOR(lastXOR, i + 1);
lastXOR = currentXOR;
}
} catch (Exception e) {
System.out.println("Error Found : -" + e);
}
return lastXOR;
}
System.out.println("Input is not in the range or valid");
return -1;
}
private static boolean isValidatedInput(int M, int N) {
if (0 <= M && 0 <= N && M <= Math.pow(10, 9) && N <= Math.pow(10, 9) && M <= N) {
return true;
} else
return false;
}
private static Integer computeXOR(Integer m, Integer n) {
return m ^ n;
}

Answer 1

它具有 O(2( 的常量时间复杂度和 O(8( 的常量空间复杂度 您可以使用以下解决方案，

public class XorOps {
public static void main(String[] args) {
System.out.println(getXor(5, 8));
}
static long getMod4(int a) {
long[] res = {a, 1, a + 1, 0};
return res[a % 4];
}
static long getXor(int a, int b) {
return getMod4(b) ^ getMod4(a - 1);
}
}

一般范围为 [5,8]。我们可以使用getXor()来查找 [0,5-1]=[0,4] 和 [0,8] 的异或。由于任何与自身的异或值都是零，因此 f(5-1( 只是抵消了异或运行小于 5 的所有值，留下范围 [5,8] 的异或。