資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告