ผลรวมเท่ากับ XOR (Equal Sum and XOR) ใน C++

ปัญหา

ได้รับจำนวนเต็ม n หาจำนวนจำนวนเต็ม i (0 ≤ i ≤ n) ที่ทำให้ (n + i) = (n ^ i)

ตัวอย่าง

อินพุต: n = 4

เอาต์พุต: 4

คำอธิบาย: i = 0,1,2,3 ตรงเงื่อนไข (4+0=4^0, 4+1=4^1, 4+2=4^2, 4+3=4^3) แต่ i=4 ไม่ตรง

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force วนลูป i=0 ถึง n ตรวจสอบ (n+i) == (n^i)

วิธีที่ 2: ทฤษฎีบิต (Bitwise) สังเกตว่า (n+i) = (n^i) ⟺ (n & i) = 0 หมายถึง บิตของ n และ i ไม่มีบิต 1 ทับซ้อนกัน จำนวนคำตอบ = 2^(จำนวนบิต 0 ใน n)

โปรแกรมตัวอย่าง (วิธีที่ 2 - มีประสิทธิภาพ)

#include <iostream>
using namespace std;

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

int main() {
    int n = 6;
    cout << "The count of integers with equal sum and XOR is " 
         << countValuesWithEqualSumXOR(n);
    return 0;
}

ผลลัพธ์

The count of integers with equal sum and XOR is 2