C++を使用してn=x +nxの解の数を見つける

この記事では、方程式n =x +n⊕xの解の数を見つけます。つまり、n =x+n⊕xとなるような与えられた値nで可能なxの値の数を見つける必要があります。ここで⊕はXOR演算を表します。 。

次に、適切な例を使用して、n =x+n⊕xの解の数に関する完全な情報について説明します。

ブルートフォース方式

解の数を見つけるためにブルートフォースアプローチを簡単に使用できます。つまり、与えられたnの値に対して、0から始まるxのすべての整数値を適用し、方程式が満たされるかどうかを検証します。xの値は次の値以下である必要があります。 nより大きい値を（n⊕x）で追加しても、答えとしてnが返されることはありません。

例

n =3の場合のxの値を1つ見つけますか？

   n = x + n ⊕ x
Putting x = 0,
   3 = 0 + 3 ⊕ 0
3 ⊕ 0 = 3,
   3 = 3
   LHS = RHS(x = 0 satisfy the equation)
So, x = 0 is one of the solution

例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n = 3, c=0;
    for (int x = 0; x <= n; ++x)// loop for giving value of x from 0 to n
        if (n == x + n ^ x)//checking if value of x satisfies the equation
            ++c;
    cout  << "Number of possible solutions : " << c;
    return 0;
}

出力

Number of possible solutions : 4

これは、ブルートフォース法を適用してn =x+n⊕xの解の数を見つける単純なC++プログラムです。

効率的なアプローチ

このアプローチでは、 nを見ると バイナリ形式では、1に設定されているビット数を見つける必要があります。方程式を見ると、nが設定されている場合、xが設定されるか n 1⊕1=0であるため、⊕xが設定されます。これは、n⊕xに設定されていないことを意味します。これで、nのすべての設定ビットの順列の数、つまり2 ^（設定ビットの数）を結論付けることができます。 。

例

#include <bits/stdc++.h>
using namespace std;
int main (){
    int n = 3, no_of_setbits = 0;    // initialising n with value and taking count of set bits as 0
    while (n != 0){
        no_of_setbits = no_of_setbits + (n % 2);    // checking if num contains set bit.
        n = n / 2;
    }
    int result = 1 << no_of_setbits;    // calculating no. of possible solution with 2^setbits
    cout << " Number of possible solutions : " << result;
    return 0;
}

出力

Number of possible solutions : 4

プログラムの複雑さ

ここでブルートフォースを適用しているため、このアプローチの時間計算量はO（n）です。より効率的な方法を適用して、プログラムの効率を向上させることができます。

結論

この記事では、問題を解決していくつかの解決策を見つけます-

n =x+n⊕x。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチについても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。この記事がお役に立てば幸いです。