주어진 범위에서 모든 숫자의 XOR 찾기

주어진 범위에서 모든 숫자의 XOR 찾기

---

'a'와 'b'는 일반적으로 1에서 4,000,000,000 사이가 될 수있는 큰 범위 [a, b]가 제공됩니다. 주어진 범위에있는 모든 숫자의 XOR을 찾아야합니다.

이 문제는 TopCoder SRM에서 사용되었습니다. 경기에서 제출 된 솔루션 중 하나를 보았지만 어떻게 작동하는지 알 수 없습니다.

누군가가 성공적인 솔루션을 설명하는 데 도움을 줄 수 있습니까?

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

long long getXor(long long a, long long b) {
     return f(b)^f(a-1);
}

다음 getXor()은 전달 된 범위 [a, b]의 모든 숫자의 xor를 계산하는 실제 함수이며 "f ()"는 도우미 함수입니다.

---

이것은 매우 영리한 솔루션입니다. 실행중인 XOR에 결과 패턴이 있다는 사실을 이용합니다. 이 f()함수는 [0, a]에서 실행 된 XOR 총계를 계산합니다. 이 표에서 4 비트 숫자를 살펴보십시오.

0000 <- 0  [a]
0001 <- 1  [1]
0010 <- 3  [a+1]
0011 <- 0  [0]
0100 <- 4  [a]
0101 <- 1  [1]
0110 <- 7  [a+1]
0111 <- 0  [0]
1000 <- 8  [a]
1001 <- 1  [1]
1010 <- 11 [a+1]
1011 <- 0  [0]
1100 <- 12 [a]
1101 <- 1  [1]
1110 <- 15 [a+1]
1111 <- 0  [0]

첫 번째 열은 이진 표현이고 10 진수 결과 및 XOR 목록에 대한 인덱스 (a)와의 관계입니다. 이것은 모든 상위 비트가 취소되고 하위 2 비트가 매 4 주기로 발생하기 때문에 발생합니다. 따라서이 작은 조회 테이블에 도달하는 방법입니다.

이제 [a, b]의 일반적인 범위를 고려하십시오. f()[0, a-1] 및 [0, b]에 대한 XOR을 찾는 데 사용할 수 있습니다 . 자체적으로 XOR 처리 한 값은 0이므로는 f(a-1)XOR 실행의 모든 ​​값을. 미만으로 취소하여 a[a, b] 범위의 XOR을 남깁니다.

---

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

Next, we use that reversal property and commutivity to give us the magic line:

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

If you've been thinking of XOR like an add, you would've dropped in a subtract there. XOR is to XOR what add is to subtract!

How do I come up with this myself?

Remember the properties of logical operators. Work with them almost like an add or multiply if it helps. It feels unusual that and (&), xor (^) and or (|) are associative, but they are!

Run the naive implementation through first, look for patterns in the output, then start finding rules which confirm the pattern is true. Simplify your implementation even further and repeat. This is probably the route that the original creator took, highlighted by the fact that it's not completely optimal (i.e. use a switch statement rather than an array).

---

I found out that the below code is also working like the solution given in the question.

May be this is little optimized but its just what I got from observing repetition like given in the accepted answer,

I would like to know / understand the mathematical proof behind the given code, like explained in the answer by @Luke Briggs

Here is that JAVA code

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

---

I have solved the problem with recursion. I simply divide the dataset into an almost equal part for every iteration.

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

Let me know your thoughts over the solution. Happy to get improvement feedbacks. The proposed solution calculates the XOR in 0(log N) complexity.

Thank you

---

To support XOR from 0 to N the code given needed to be modified as below,

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

참고URL : https://stackoverflow.com/questions/10670379/find-xor-of-all-numbers-in-a-given-range