Đếm số x ≤ n thỏa (n XOR x) = (n - x) trong C++

Cho số n. Tìm số giá trị x ∈ [0, n] thỏa (n XOR x) = (n - x).

Ví dụ

Đầu vào − n = 10

Đầu ra − 4

Giải thích − x = 0, 2, 8, 10.

Đầu vào − n = 15

Đầu ra − 16

Giải thích − Tất cả x = 0..15 đều thỏa.

Phương pháp giải

Cách 1 (naive): Duyệt i = 0..n, kiểm tra n - i == (n ^ i).

Cách 2 (hiệu quả): Chuyển n sang nhị phân. Chỉ có 1 XOR 0 = 1-0 và 1 XOR 1 = 1-1 đúng. Với 0 XOR 0 ≠ 0-1 và 0 XOR 1 ≠ 0-1. Do đó, mỗi bit '1' trong n cho 2 lựa chọn. Nếu n có p bit 1 → kết quả = 2^p.

• Hàm count_values(int n).
• Cách 1: vòng lặp i=0..n, đếm.
• Cách 2: bitset<8>(n).to_string(), đếm số '1', trả về pow(2, count).

Ví dụ code (naive)

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

int count_values(int n) {
    int count = 0;
    for (int i = 0; i <= n; i++) {
        if (n - i == (n ^ i)) count++;
    }
    return count;
}

int main() {
    int n = 25;
    cout << "Count of values of x <= n for which (n XOR x) = (n - x) are: " << count_values(n);
    return 0;
}

Đầu ra

Count of values of x <= n for which (n XOR x) = (n - x) are: 8

Ví dụ code (hiệu quả)

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

int count_values(int n) {
    int count = 0;
    string number = bitset<8>(n).to_string();
    int length = number.length();
    for (int i = 0; i < length; i++) {
        if (number.at(i) == '1') count++;
    }
    count = (int)pow(2, count);
    return count;
}

int main() {
    int n = 25;
    cout << "Count of values of x <= n for which (n XOR x) = (n - x) are: " << count_values(n);
    return 0;
}

Đầu ra

Count of values of x <= n for which (n XOR x) = (n - x) are: 8