C++를 사용하여 n =x + n x의 해의 개수 찾기

이 기사에서 우리는 방정식 n =x + n ⊕ x의 해의 수를 찾을 것입니다. 즉, n =x + n ⊕ x가 되도록 주어진 값 n으로 가능한 x 값의 수를 찾아야 합니다. 여기서 ⊕는 XOR 연산을 나타냅니다. .

이제 적절한 예를 들어 n =x + n ⊕ x의 해의 수에 관한 완전한 정보를 논의할 것입니다.

무차별 대입법

우리는 솔루션의 수를 찾기 위해 무차별 대입 접근 방식을 사용할 수 있습니다. 즉, 주어진 n 값에 대해 0부터 시작하는 x의 모든 정수 값을 적용하고 방정식이 만족하는지 여부를 확인합니다. x 값은 다음보다 작거나 같아야 합니다. (n ⊕ x)를 사용하여 n보다 큰 값을 더하면 n이 답으로 반환되지 않기 때문입니다.

예시

n =3에 대해 x의 한 값을 찾으십니까?

   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

Brute force 방법을 적용하여 n =x + n ⊕ x의 해의 개수를 구하는 간단한 C++ 프로그램입니다.

효율적인 접근

이 접근 방식에서 n 이진 형식에서 1로 설정된 비트 수를 찾아야 하며 방정식을 보면 n이 설정되면 x가 설정되거나 n ⊕ x는 1 ⊕ 1 =0이므로 설정됩니다. 이는 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 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.