นับจำนวนที่ผลต่างกับ N เท่ากับ XOR กับ N ใน C++

ภาพรวมปัญหา

ให้จำนวน N ต้องการหาจำนวนระหว่าง 0 ถึง N ที่ทำให้ (N - i) == (N ^ i)

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

เงื่อนไข (N - i) == (N ^ i) เป็นจริงก็ต่อเมื่อ ไม่มีการยืม (borrow) ในการลบ N - i แบบไบนารี

• เกิดขึ้นเมื่อบิต 1 ของ i เป็น subset ของบิต 1 ของ N
• กล่าวคือ i & N == i (ทุกบิต 1 ของ i ต้องเป็น 1 ใน N ด้วย)

ตัวอย่าง

Input: N = 6 (110₂)

Output: 4

คำอธิบาย: 0 (000), 2 (010), 4 (100), 6 (110) — บิต 1 เป็น subset ของ 110

Input: N = 20 (10100₂)

Output: 4

คำอธิบาย: 0, 4 (00100), 16 (10000), 20 (10100)

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

1. นับจำนวนบิต 1 ใน N
2. คำตอบ = 2^(จำนวนบิต 1) — เพราะแต่ละบิต 1 สามารถเลือกเอาไว้ใน i หรือไม่ได้อิสระ

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

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

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

int main() {
    int N = 15;
    cout << "Count: " << diffisXOR(N);
    return 0;
}

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

int diffisXOR_fast(int n) {
    int oneBits = __builtin_popcount(n); // GCC/Clang
    // หรือนับเอง:
    // int oneBits = 0;
    // while (n) { oneBits += n & 1; n >>= 1; }
    return 1 << oneBits;
}

ผลลัพธ์

Count of numbers whose difference with N == XOR with N: 16

ความซับซ้อน

ความสัมพันธ์กับปัญหาอื่น

ปัญหานี้เกี่ยวข้องกับ "นับ subset ของบิต 1" ซึ่งเทียบเท่ากับการนับ i ที่ i & N == i