นับจำนวนที่ผลรวมกับ X เท่ากับ XOR กับ X ใน C++

ภาพรวมปัญหา

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

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

เงื่อนไข (X + i) == (X ^ i) เป็นจริงก็ต่อเมื่อ ไม่มีการพก (carry) ในการบวก X + i แบบไบนารี

• เกิดขึ้นเมื่อ X และ i ไม่มีบิต 1 ตรงตำแหน่งเดียวกัน
• กล่าวคือ X & i == 0
• นี่คือเงื่อนไขเดียวกับปัญหา OR == XOR (xID 1004079033)

ตัวอย่าง

Input: X = 6 (110₂)

Output: 2

คำอธิบาย: 0 (000), 1 (001)

Input: X = 20 (10100₂)

Output: 8

คำอธิบาย: 0,1,2,3,8,9,10,11

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

เหมือนกับ xID 1004079033 ทุกประการ

1. นับจำนวนบิต 0 ใน X
2. คำตอบ = 2^(จำนวนบิต 0)

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

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

int sumisXOR(int x) {
    int count = 0;
    for (int i = 0; i <= x; i++) {
        if ((i + x) == (i ^ x)) count++;
    }
    return count;
}

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

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

int sumisXOR_fast(int x) {
    int zeroBits = 0;
    int temp = x;
    while (temp > 0) {
        if ((temp & 1) == 0) zeroBits++;
        temp >>= 1;
    }
    return 1 << zeroBits;
}

ผลลัพธ์

Count of numbers whose sum with X == XOR with X: 1

ความสัมพันธ์ระหว่างปัญหา

ความซับซ้อน

• เวลา: O(log X) ด้วยวิธีนับบิต
• พื้นที่: O(1)