C ++中给定范围[L，R]中所有元素的XOR
在这个问题中，我们得到两个整数L和R来表示一个范围。我们的任务是找到[L，R]范围内所有元素的异或。
让我们举个例子来了解这个问题，
输入-L = 3，R = 6
说明-3 ^ 4 ^ 5 ^ 6 =
为了解决这个问题，我们将找到R的MSB。答案的MSB将不大于R。现在，我们将找到从0到MSB的位数的奇偶校验。
现在，要找到第i个位的奇偶校验计数，我们可以看到第i个位的状态将在每第2个数字上变化。L到R范围内的所有ith位设置都相同。这样做时，会出现两种情况-
情况1（i！= 0） -检查L的第i位。如果已设置，则检查L和L + 2i之间的数字的奇偶校验计数。如果设置了L的第i位，则L为奇数，则计数为奇数，否则为偶数。现在，我们将移至R，并确定R-2i和R之间的许多元素的计数奇偶性，并采用相同的方法。
其余所有整数都不会考虑，因为它们甚至会生成设置了第i位的整数。
情况2（i = 0） -在这里，我们将不得不请看以下情况-
情况2.1 -L和R均为奇数，计数设置为第0位的整数的个数为(RL)/ 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
以上是 C ++中给定范围[L，R]中所有元素的XOR 的全部内容， 来源链接： utcz.com/z/351443.html
