Tìm số nghiệm của phương trình n = x + n XOR x bằng C++

Trong bài viết này, chúng ta tìm số nghiệm của phương trình n = x + (n XOR x), với n cho trước, x là biến cần tìm. Phép XOR (^) trả về 1 khi hai bit khác nhau, 0 khi giống nhau.

Phương pháp Brute Force

Duyệt x từ 0 đến n, kiểm tra điều kiện n == x + (n ^ x).

Ví dụ

n = 3, x = 0: 3 = 0 + (3 ^ 0) = 3 ✓
Số nghiệm = 4 (với n=3)

Mã nguồn Brute Force

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3, c = 0;
    for (int x = 0; x <= n; ++x)
        if (n == x + (n ^ x))
            ++c;
    cout << "Số nghiệm có thể: " << c;
    return 0;
}

Kết quả

Số nghiệm có thể: 4

Phương pháp hiệu quả (Dựa trên bit)

Xét n dưới dạng nhị phân. Với mỗi bit 1 của n, hoặc x có bit 1 hoặc n XOR x có bit 1 (không thể cả hai cùng 1 vì 1^1=0). Do đó, mỗi bit 1 của n cho 2 lựa chọn cho bit tương ứng của x. Số nghiệm = 2^(số bit 1 của n).

Mã nguồn hiệu quả

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 3, no_of_setbits = 0;
    while (n != 0) {
        no_of_setbits = no_of_setbits + (n % 2);
        n = n / 2;
    }
    int result = 1 << no_of_setbits; // 2^số bit 1
    cout << "Số nghiệm có thể: " << result;
    return 0;
}

Kết quả

Số nghiệm có thể: 4

Độ phức tạp

Brute Force: O(N). Phương pháp bit: O(log N) - nhanh hơn đáng kể.

Kết luận

Bài viết giải quyết bài toán tìm số nghiệm của n = x + n XOR x. Phương pháp tối ưu dựa trên số bit 1 của n cho độ phức tạp O(log N). Mã nguồn C++ đầy đủ cho cả hai cách. Có thể triển khai bằng các ngôn ngữ khác.