C++에서 주어진 범위 [L, R]에 있는 모든 요소의 XOR

이 문제에서는 범위를 나타내는 두 개의 정수 L과 R이 제공됩니다. 우리의 임무는 [L, R] 범위 내의 모든 요소의 xor를 찾는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - L=3, R =6

설명 − 3^4^5^6 =

이 문제를 해결하기 위해 우리는 R의 MSB를 찾을 것입니다. 답의 MSB는 R보다 크지 않을 것입니다. 이제 0에서 MSB까지의 비트 수 카운트의 패리티를 찾을 것입니다.

이제 i번째 비트의 패리티 카운트를 찾기 위해 i번째 비트의 상태가 2번째 숫자마다 변경됨을 알 수 있습니다. L ~ R 범위의 모든 i번째 비트에 대해서도 마찬가지입니다. 이렇게 하면 두 가지 경우가 발생합니다. -

사례 1(i !=0) − L의 i번째 비트를 확인합니다. 설정되어 있으면 L과 L+2i 사이의 수의 패리티 카운트를 확인합니다. 그리고 L의 i번째 비트가 설정되면 L은 홀수이고 카운트는 홀수이고 그렇지 않으면 짝수입니다. 이제 R로 이동하여 R-2i와 R 사이의 요소 개수의 패리티를 결정하고 동일한 방법을 따릅니다.

나머지 모든 정수는 i번째 비트가 설정된 정수의 개수까지 생성하므로 고려 대상이 아닙니다.

사례 2(i =0) − 여기에서 다음 경우를 고려해야 합니다. −

사례 2.1 − L과 R 모두 홀수, 0번째 비트 세트가 있는 정수의 개수는 (R-L)/2+1이 됩니다. .

사례 2.2 − 그렇지 않으면 카운트는 (R-L+1)/2 의 숫자로 내림됩니다. .

예시

솔루션 구현을 보여주는 프로그램,

#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<<"The XOR of all element within the range ("<<L<<", "<<R<<") is : "<<XOREleInRange(L, R);
   return 0;
}

출력

The XOR of all element within the range (1, 4) is : 4