C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C ++の指定された範囲[L、R]のすべての要素のXOR

この問題では、範囲を示す2つの整数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番目のビットについても同じです。これを行うと、2つのケースが発生します-

ケース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

  1. C++の特定のノードのサブツリー内のすべてのノードのXOR

    この問題では、nツリーが与えられ、ツリーのノードであるクエリがいくつかあります。私たちのタスクは、指定されたノードによって形成されたサブツリーのすべてのノードのXORを出力することです。 問題を理解するために例を見てみましょう クエリ − {1、6、5} 出力 − 0 0 5 説明 − 1^6^3^2^4^7^5 6^2^4 5 この問題を解決するために、ツリーを1回トラバースして保存することにより、サブツリーのすべてのノードのxorを計算します。ここで、子ノードの場合はサブツリーのすべてのノードのxorを計算し、次に指定されたすべてのサブツリーを計算します。結果を保存す

  2. Python –指定された範囲のリスト内のすべての偶数要素をテストします

    リスト内のすべての偶数要素を特定の範囲でテストする必要がある場合は、単純な反復と剰余演算子が使用されます。 以下は同じのデモンストレーションです- 例 my_list = [32, 12, 42, 61, 58, 60, 19, 16] print("The list is :") print(my_list) i, j = 2, 7 my_result = True for index in range(i, j + 1):    if my_list[index] % 2 :       my_result =