数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中给定范围[L, R]内所有元素的异或
在这个问题中，我们给定两个整数 L 和 R，表示一个范围。我们的任务是找到范围 [L, R] 内所有元素的异或。
让我们举个例子来理解这个问题，
输入 − L=3, R = 6
说明 − 3^4^5^6 =
为了解决这个问题，我们将找到 R 的最高有效位 (MSB)。答案的 MSB 将不会大于 R。现在，我们将找到从 0 到 MSB 的位数的奇偶校验计数。
现在，为了找到第 i 位的奇偶校验计数，我们可以看到第 i 位的状态将在每 2i 个数字上改变一次。对于范围 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
更新于: 2020-04-20
575 次查看
广告