FatalError의 훌륭한 답변에 추가하면 라인을 return f(b)^f(a-1);더 잘 설명 할 수 있습니다. 간단히 말해 XOR에는 다음과 같은 훌륭한 속성이 있기 때문입니다.

• 그것은의 연관 – 장소 브래킷 어디든지 당신이 원하는
• 그건 교환 법칙이 성립 – 수단은 당신이 주변에 연산자를 이동할 수 있습니다 (그들이 할 수있는 “통근”)

두 가지 모두 작동합니다.

(a ^ b ^ c) ^ (d ^ e ^ f) = (f ^ e) ^ (d ^ a ^ b) ^ c

• 그것은 그 자체를 반전

이렇게 :

a ^ b = c
c ^ a = b

더하기와 곱하기는 다른 연관 / 교환 연산자의 두 가지 예이지만, 그 자체를 뒤집지는 않습니다. 좋습니다. 이러한 속성이 왜 중요한가요? 글쎄요, 간단한 방법은 그것을 실제 상태로 확장하는 것입니다. 그러면 여러분은 이러한 속성을 직장에서 볼 수 있습니다.

먼저 우리가 원하는 것을 정의하고 그것을 n이라고 부릅시다 :

n      = (a ^ a+1 ^ a+2 .. ^ b)

도움이된다면 XOR (^)을 추가 한 것처럼 생각하십시오.

함수를 정의 해 보겠습니다.

f(b)   = 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ b

b는보다 큽니다 a. 따라서 몇 개의 추가 괄호 (연관 적이므로 가능함)를 안전하게 넣어서 다음과 같이 말할 수도 있습니다.

f(b)   = ( 0 ^ 1 ^ 2 ^ 3 ^ 4 .. ^ (a-1) ) ^ (a ^ a+1 ^ a+2 .. ^ b)

다음을 단순화합니다.

f(b)   = f(a-1) ^ (a ^ a+1 ^ a+2 .. ^ b)

f(b)   = f(a-1) ^ n

다음으로, 우리는 그 반전 속성과 commutivity를 사용하여 우리에게 마법의 선을줍니다.

n      = f(b) ^ f(a-1)

XOR을 더하기처럼 생각했다면 거기에 빼기를 떨어 뜨렸을 것입니다. XOR은 XOR에 추가하는 것입니다.

이걸 어떻게 생각해?

논리 연산자의 속성을 기억하십시오. 도움이된다면 더하기 또는 곱하기와 같이 작업하십시오. and (&), xor (^) 및 or (|)가 연관성이 있다는 것은 이상하게 느껴지지만 그렇습니다!

먼저 순진한 구현을 실행하고 출력에서 ​​패턴을 찾은 다음 패턴이 참인지 확인하는 규칙을 찾기 시작합니다. 구현을 더욱 단순화하고 반복하십시오. 이것은 아마도 완전히 최적이 아니라는 사실에 의해 강조된 원래 제작자가 취한 경로 일 것입니다 (예 : 배열보다는 switch 문 사용).

답변

public int findXORofRange(int m, int n) {
    int[] patternTracker;

    if(m % 2 == 0)
        patternTracker = new int[] {n, 1, n^1, 0};
    else
        patternTracker = new int[] {m, m^n, m-1, (m-1)^n};

    return patternTracker[(n-m) % 4];
}

public int recursion(int M, int N) {
    if (N - M == 1) {
        return M ^ N;
    } else {
        int pivot = this.calculatePivot(M, N);
        if (pivot + 1 == N) {
            return this.recursion(M, pivot) ^ N;
        } else {
            return this.recursion(M, pivot) ^ this.recursion(pivot + 1, N);
        }
    }
}
public int calculatePivot(int M, int N) {
    return (M + N) / 2;
}

int f(int a) {
    int []res = {a, 1, a+1, 0};
    return res[a % 4];
}

int getXor(int a, int b) {
    return f(b) ^ f(a);
}