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

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 3 年前。

Improve this question

找到一个范围的按位异或，例如 (5,8) --> 5 bitXOR 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] 的异或。