Trong bài này, chúng ta sẽ tìm số nghiệm của phương trình n =x + n ⊕ x, tức là chúng ta cần tìm số giá trị của x có thể có với giá trị n cho trước sao cho n =x + n ⊕ x trong đó ⊕ biểu diễn phép toán XOR .
Bây giờ chúng ta sẽ thảo luận về thông tin đầy đủ về số nghiệm của n =x + n ⊕ x với một ví dụ thích hợp.
Phương pháp vũ phu
Chúng ta có thể đơn giản sử dụng cách tiếp cận brute force để tìm số nghiệm, tức là với giá trị cho trước của n, chúng ta áp dụng mọi giá trị nguyên của x bắt đầu từ 0 và xác minh xem phương trình có thỏa mãn hay không, giá trị của x phải nhỏ hơn hoặc bằng n bởi vì việc thêm giá trị lớn hơn n với (n ⊕ x) sẽ không bao giờ trả về n là câu trả lời.
Ví dụ
Tìm một giá trị của x để n =3?
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
Ví dụ
#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;
} Đầu ra
Number of possible solutions : 4
Đây là chương trình C ++ đơn giản để tìm số nghiệm của n =x + n ⊕ x bằng cách áp dụng phương pháp Brute force.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, nếu chúng ta xem xét n ở dạng nhị phân, chúng ta cần tìm số bit được đặt thành 1 và nhìn vào phương trình, chúng ta có thể nói nếu n được đặt thì x sẽ được đặt hoặc n ⊕ x sẽ được đặt vì 1 ⊕ 1 =0. Có nghĩa là n ⊕ x không có nó được đặt, vì vậy bây giờ chúng ta có thể kết luận số lượng hoán vị cho mọi bit đặt trong n, tức là, 2 ^ (số bit đặt ).
Ví dụ
#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;
} Đầu ra
Number of possible solutions : 4
Độ phức tạp của chương trình
Độ phức tạp về thời gian của phương pháp này là O (n), vì chúng ta đang áp dụng Brute force ở đây. Chúng tôi có thể áp dụng các phương pháp hiệu quả hơn để nâng cao hiệu quả của chương trình.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để tìm ra một số giải pháp -
n =x + n ⊕ x. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Hy vọng bạn thấy bài viết này hữu ích.