นับจำนวนที่ OR กับ N เท่ากับ XOR กับ N ใน C++

ภาพรวมปัญหา

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

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

เงื่อนไข (N | i) == (N ^ i) เป็นจริงก็ต่อเมื่อ N และ i ไม่มีบิต 1 ตรงตำแหน่งเดียวกัน

• N | i = 1 ก็ต่อเมื่อ N=1 หรือ i=1 (หรือทั้งคู่)
• N ^ i = 1 ก็ต่อเมื่อ N และ i ต่างกัน (หนึ่งเป็น 1 อีกหนึ่งเป็น 0)
• ทั้งสองเท่ากันได้ก็ต่อเมื่อไม่มีบิตที่ N=1 และ i=1 พร้อมกัน

กล่าวคือ i ต้องมีบิต 1 เฉพาะตำแหน่งที่ N มีบิต 0 เท่านั้น

ตัวอย่าง

Input: N = 6 (110₂)

Output: 2

คำอธิบาย: จำนวนคือ 0 (000), 1 (001) — บิต 1 อยู่ที่ N เป็น 0 เท่านั้น

Input: N = 20 (10100₂)

Output: 8

คำอธิบาย: 0,1,2,3,8,9,10,11 (บิต 1 อยู่ที่ตำแหน่ง 0,1,3 เท่านั้น)

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

1. นับจำนวนบิต 0 ใน N (นับแค่บิตที่มีนัยสำคัญ ไม่นับ leading zeros)
2. คำตอบ = 2^(จำนวนบิต 0)
3. รวม i=0 ด้วยเสมอ

โค้ดตัวอย่าง (Naive - ตรวจสอบทุกตัว)

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

int orisXOR(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: " << orisXOR(N);
    return 0;
}

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

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

ผลลัพธ์

Count of numbers whose OR with N == XOR with N: 1

ความซับซ้อน