C++で（n XOR x）=（n – x）であるx<=nの値の数

入力として数値nが与えられます。目標は、条件（n xor x）=（nx）が成り立つような値xを見つけることです。また、xは範囲[0、n]にあります。

例を挙げて理解しましょう

入力 − n =10

出力 −（n XOR x）=（n – x）が− 4

説明 −10xまたはx=10-x − 0、2、8、および10のxの値。

入力 − n =15

出力 −（n XOR x）=（n – x）が-16であるx<=nの値の数

説明 − xの値（15 xor x =15-x − 0、1、2、3、4、5、6、7、8、9、10、11、12、13、14、および15）。

以下のプログラムで使用されているアプローチは次のとおりです

2つのアプローチを使用します。 forループを使用した最初の素朴なアプローチ。可能な限りxについて、i=0からi<=nまでトラバースを開始します。ここで、（n --i ==（n ^ i）// xor）かどうかを確認します。真のインクリメントカウントの場合。

• 整数変数nを入力として受け取ります。

• 関数unique_pair（int arr []、int size）は、配列とその長さを受け取り、ペア（arr [i]、arr [j]）でインデックスi となるような一意のペアの数を返します。

• countの初期値を0とします。

• 整数のペアを含むセット「se」を取ります。 （set > se）

• 2つのforループを使用してarr[]のトラバースを開始します。 i=0からi

• 各ペアは常にiを使用してペア（arr [i]、arr [j]）を「se」に追加します。

• 両方のforループの最後で、count =se.size（）を更新します。

• Countには、「se」にいくつかのペアが含まれるようになりました。 （すべてが一意です。）

• 結果としてカウントを返します。

効率的なアプローチ

このアプローチでは、最初にnを同等のバイナリに変換します。私たちはそれを知っています

1 xor 0 =1-0

1 xor 1 =1-1

しかし

0xor0≠0-1

0xor1≠0-1

したがって、nのバイナリ表現の1ごとに、2つのケースがあります。 nのバイナリ表現のpの場合、条件を満たす2pの値があります。

インデックスi。次に、そのようなカウントを個別に追加して、一意のペアの総数を求めます。

• 整数変数nを入力として受け取ります。

• 関数unique_pair（int arr []、int size）は、配列とその長さを受け取り、ペア（arr [i]、arr [j]）でインデックスi となるような一意のペアの数を返します。

• countの初期値を0とします。

• number =bitset <8>（n）.to_string（）;

  を使用してnを文字列に変換します

• length =number.length（）を取ります。

• インデックスi=0からi

• count =pow（2、count）をxの最終値として設定します。

• 結果としてカウントを返します。

例（素朴なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   for (int i = 0; i <= n; i++){
      if (n - i == (n ^ i)){
         count++;
      }
   }
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of values of x <= n for which (n XOR x) = (n – x) are: 8

例（効率的なアプローチ）

#include<bits/stdc++.h>
using namespace std;
int count_values(int n){
   int count = 0;
   string number = bitset<8>(n).to_string();
   int length = number.length();
   for (int i = 0; i < length; i++){
      if (number.at(i) == '1')
         { count++; }
   }
   count = (int)pow(2, count);
   return count;
}
int main(){
   int n = 25;
   cout<<"Count of values of x <= n for which (n XOR x) = (n – x) are: "<<count_values(n);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of values of x <= n for which (n XOR x) = (n – x) are: 8