Using C++ programming, find the number of solutions to the equation n = x + n * x

In this article we will find the number of solutions to the equation n = x n ⊕ x, i.e. we need to find the number of possible values ​​of x for a given value n such that n = x n ⊕ x, where ⊕ represents the XOR operation.

Now we will discuss complete information about the number of solutions for n = x n ⊕ x and provide appropriate examples.

Brute force method

We can simply use the brute force method to find the number of solutions, i.e. for a given value of n, we apply each integer value of x starting from 0, and verify the equation To be satisfied, the value of x should be less than or equal to n, since adding a value greater than n to (n ⊕ x) will never return n as the answer.

Example

Find a value of x such that n = 3 holds? The Chinese translation of

   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

Example

is:

Example

#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;
}

Output

Number of possible solutions : 4

This is a simple C program that finds n by applying a brute force method = x n ⊕ The number of solutions to x.

Efficient method

In this method, if we look at the binary form of n, we need to find the number of bits set to 1, and according to the equation, we We can say that if n is set, then either x is set or n ⊕ x is set, since 1 ⊕ 1 = 0. This means that n ⊕ x is not set, so now we can conclude that for each set bit in n, the number of permutations is 2^(number of set bits).

The Chinese translation of Example

is:

Example

#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;
}

Output

Number of possible solutions : 4

Complexity of Program

The time complexity of this approach is O(n), as we are applying Brute force here. We can apply more efficient methods to improve the efficiency of the program.

Conclusion

In this article, we solve a problem to find a number of solution −

n = x n ⊕ x. We also learned the C program for this problem and the complete approach by which we solved this problem. We can write the same program in other languages ​​such as C, java, python, and other languages. Hope you find this article helpful.

The above is the detailed content of Using C++ programming, find the number of solutions to the equation n = x + n * x. For more information, please follow other related articles on the PHP Chinese website!