นับคู่มี序ที่ผลรวมเป็น S และ XOR เป็น K ใน C++

ภาพรวมปัญหา

ให้จำนวน S และ K ต้องการนับคู่มี序ของจำนวนเต็มบวก (i, j) ที่ i + j = S และ i ^ j = K

ตัวอย่าง

Input: S = 10, K = 4

Output: 2

คำอธิบาย: (3,7) และ (7,3)

Input: S = 12, K = 6

Output: 0

ข้อสังเกตสำคัญ

สำหรับจำนวนเต็มบวก a, b:

• a + b = (a ^ b) + 2 × (a & b)
• ดังนั้น S = K + 2 × (a & b)
• เงื่อนไข: S ≥ K และ (S - K) ต้องเป็นเลขคู่
• ให้ C = (S - K) / 2 = a & b
• ต้องมี C & K = 0 (บิต 1 ของ C และ K ไม่ทับกัน)

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

1. ถ้า S < K หรือ (S - K) % 2 != 0 → คืนค่า 0
2. C = (S - K) / 2
3. ถ้า (C & K) != 0 → คืนค่า 0
4. จำนวนคู่ = 2^(จำนวนบิต 1 ใน K) — แต่ละบิต 1 ของ K สามารถมาจาก a หรือ b ได้
5. เพราะนับคู่มี序 (a,b) และ (b,a) แยกกัน

โค้ดตัวอย่าง (Naive - 2 Loops)

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

int sumXOR(int s, int k) {
    int count = 0;
    for (int i = 1; i < s; i++) {
        for (int j = i + 1; j < s; j++) {
            if (i + j == s && (i ^ j) == k) {
                count += 2; // (i,j) และ (j,i)
            }
        }
    }
    return count;
}

int main() {
    int S = 9, K = 5;
    cout << "Ordered pairs: " << sumXOR(S, K);
    return 0;
}

โค้ดที่ปรับปรุงแล้ว O(log S)

int sumXOR_fast(int s, int k) {
    if (s < k) return 0;
    if ((s - k) % 2 != 0) return 0;
    
    int c = (s - k) / 2;
    if ((c & k) != 0) return 0;
    
    int oneBits = __builtin_popcount(k);
    return 1 << oneBits; // 2^oneBits
}

ผลลัพธ์

Ordered pairs such that sum is S and XOR is K: 4

ความซับซ้อน

ตัวอย่างการตรวจสอบ

S=10, K=4: S-K=6 (คู่), C=3 (011), K=4 (100), C&K=0 ✓

oneBits(K)=1 → 2¹=2 คู่: (3,7), (7,3) ✓