문제 소개
이 문제에서는 하나의 구간을 나타내는 두 정수 L과 R이 주어지며, [L, R] 범위에 포함된 모든 정수를 차례대로 XOR 연산한 결과를 구하는 것이 목표입니다.
예시
입력: L = 3, R = 6
출력: 4
풀이: 3 ^ 4 ^ 5 ^ 6 = 4
접근 방법: 비트 단위 분석
범위의 모든 숫자를 하나씩 XOR하는 대신, 각 비트 자리별로 생각하면 실행 시간을 크게 줄일 수 있습니다.
- 먼저 R의 MSB(최상위 비트) 위치를 구합니다. 정답의 MSB는 R의 MSB보다 클 수 없습니다.
- 0부터 MSB까지 각 비트 i에 대해, [L, R] 범위 안에서 i번째 비트가 1로 설정된 숫자의 개수가 홀수인지 짝수인지(패리티)를 판별합니다.
- i번째 비트는 2i 간격으로 주기적으로 0과 1이 반복됩니다. 따라서 범위의 양끝(L 근처와 R 근처)만 살펴보면 충분합니다.
경우 1: i > 0인 비트
L의 i번째 비트가 이미 1로 설정되어 있다면, L부터 L + 2i 구간에서 해당 비트가 설정된 숫자의 개수를 세어 홀짝성을 확인합니다. L이 홀수면 개수는 홀수, 그렇지 않으면 짝수입니다. 같은 방식으로 R 쪽에서도 R − 2i부터 R 구간을 검사합니다.
나머지 중간 구간의 정수들은 고려하지 않아도 됩니다. 이들은 i번째 비트가 1인 숫자를 항상 짝수 개씩 만들어내므로 XOR 결과에 아무런 영향을 주지 않기 때문입니다.
경우 2: i = 0 (최하위 비트)
최하위 비트는 매 숫자마다 0과 1이 번갈아 나타나므로 다음과 같이 나누어 처리합니다.
- 경우 2.1: L과 R이 둘 다 홀수라면, 0번째 비트가 설정된 숫자의 개수는 (R − L) / 2 + 1개입니다.
- 경우 2.2: 그 밖의 경우에는 (R − L + 1) / 2의 내림값이 개수가 됩니다.
C++ 구현 예제
위 접근 방식을 구현한 프로그램입니다.
#include <iostream>
using namespace std;
int findMSB(int x) {
int ret = 0;
while ((x >> (ret + 1)) != 0)
ret++;
return ret;
}
int XOREleInRange(int L, int R) {
int max_bit = findMSB(R);
int mul = 2;
int ans = 0;
for (int i = 1; i <= max_bit; i++) {
if ((L / mul) * mul == (R / mul) * mul) {
if (((L & (1 << i)) != 0) && (R - L + 1) % 2 == 1)
ans += mul;
mul *= 2;
continue;
}
bool oddCount = 0;
if (((L & (1 << i)) != 0) && L % 2 == 1)
oddCount = (oddCount ^ 1);
if (((R & (1 << i)) != 0) && R % 2 == 0)
oddCount = (oddCount ^ 1);
if (oddCount)
ans += mul;
mul *= 2;
}
int zero_bit_cnt = zero_bit_cnt = (R - L + 1) / 2;
if (L % 2 == 1 && R % 2 == 1)
zero_bit_cnt++;
if (zero_bit_cnt % 2 == 1)
ans++;
return ans;
}
int main(){
int L = 1, R = 4;
cout<<"범위 ("<<L<<", "<<R<<") 내 모든 숫자의 XOR : "<<XOREleInRange(L, R);
return 0;
}
실행 결과
범위 (1, 4) 내 모든 숫자의 XOR : 4
결과 검증: 1 ^ 2 ^ 3 ^ 4 = 4이므로 올바른 출력임을 확인할 수 있습니다. 이 알고리즘은 각 비트를 한 번씩만 검사하므로 O(log R)의 시간 복잡도로 동작하며, 범위가 매우 넓은 경우에도 빠르게 답을 구할 수 있습니다.