Tổng bằng XOR (Equal Sum and XOR) trong C++

Cho số nguyên n. Tìm số lượng số nguyên i (0 ≤ i ≤ n) thỏa mãn: n + i = n ^ i (trong đó ^ là phép XOR bitwise).

Ví dụ minh họa

Đầu vào: n = 4

Đầu ra: 4

Giải thích:

i=0: 4+0=4, 4^0=4 (Đúng)
i=1: 4+1=5, 4^1=5 (Đúng)
i=2: 4+2=6, 4^2=6 (Đúng)
i=3: 4+3=7, 4^3=7 (Đúng)
i=4: 4+4=8, 4^4=0 (Sai)
=> Có 4 giá trị.

Phương pháp giải & Quan sát quan trọng

n + i = n ^ i <=> n & i = 0 (Không có bit 1 nào chung ở cùng vị trí).

Điều này có nghĩa là tại mọi vị trí bit mà n có bit 1, i phải có bit 0. Tại các vị trí n có bit 0, i có thể là 0 hoặc 1.

Suy ra: Số lượng giá trị i hợp lệ = 2^(số bit 0 của n).

Chương trình minh họa (Tối ưu O(log N))

#include <iostream>
using namespace std;

int countValuesWithEqualSumXOR(int n) {
    int unsetBits = 0;
    while (n > 0) {
        if ((n & 1) == 0) unsetBits++;
        n >>= 1;
    }
    return 1 << unsetBits; // 2 ^ unsetBits
}

int main() {
    int n = 6; // nhị phân 110 -> 1 bit 0 -> 2^1 = 2 giá trị (i=0, i=1)
    cout << "So luong i thoa man: " << countValuesWithEqualSumXOR(n);
    return 0;
}

Đầu ra

So luong i thoa man: 2

Chương trình tham khảo (Vét cạn O(N) - Chỉ để kiểm tra)

// Chỉ dùng cho n nhỏ
int countBruteForce(int n) {
    int cnt = 0;
    for (int i = 0; i <= n; i++)
        if ((n + i) == (n ^ i)) cnt++;
    return cnt;
}