[백준] 10464 (XOR)

해설

임의의 짝수와 바로 다음 홀수에 대해, 두 수는 마지막 비트를 제외한 앞부분이 모두 같기 때문에 $(2k) \oplus (2k + 1) = 1$이 성립합니다.

따라서 0부터 $N$까지의 모든 정수를 XOR한 결과는 $N$을 4로 나눈 나머지에 따라서만 달라집니다.

• $N \mod 4 = 0$: $0 \oplus N = N$
• $N \mod 4 = 1$: $(N - 1) \oplus N = 1$
• $N \mod 4 = 2$: $(N - 2) \oplus (N - 1) \oplus N = N + 1$
• $N \mod 4 = 3$: $(N - 3) \oplus (N - 2) \oplus (N - 1) \oplus N = 0$

이제, $S$부터 $F$까지의 모든 정수를 XOR한 결과는 $0 \oplus 1 \oplus \cdots \oplus (S - 1)$, $0 \oplus 1 \oplus \cdots \oplus F$를 각각 계산한 뒤 결과를 XOR하여 상쇄시키는 방식으로 구할 수 있습니다.