XOR ของจำนวน 0 และ 1 ใน Binary Representation (C++)

โจทย์

ได้รับตัวเลข ต้องการหา XOR ของจำนวนบิต 0 และบิต 1 ใน binary representation ของตัวเลขนั้น

ตัวอย่าง

Input: n = 9
Binary: 1001
Count of 0s: 2
Count of 1s: 2
Output: 2 ^ 2 = 0

อัลกอริทึม

1. วนลูปดึงบิตทีละบิต (n % 2 หรือ n & 1)
2. นับจำนวน 0s และ 1s
3. Shift right (n /= 2 หรือ n >>= 1)
4. ทำซ้ำจน n = 0
5. คืนค่า count0 ^ count1

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

#include <iostream>
using namespace std;

int countXOR10(int n) {
    int count0s = 0, count1s = 0;
    
    while (n) {
        if (n & 1) count1s++;
        else count0s++;
        n >>= 1;  // หรือ n /= 2
    }
    
    return count0s ^ count1s;
}

int main() {
    int n = 21;  // 10101
    cout << "XOR of count of 0s and 1s in binary of " << n << " is " << countXOR10(n);
    return 0;
}

ผลลัพธ์

XOR of count of 0s and 1s in binary of 21 is 1

ตรวจสอบ: 21 = 10101₂ → 1s: 3, 0s: 2 → 3 ^ 2 = 1 ✓

Edge Cases

หมายเหตุ: สำหรับ n=0 โค้ดข้างต้นจะคืน 0 (เพราะ while loop ไม่รัน) ควรเพิ่ม special case:

int countXOR10(int n) {
    if (n == 0) return 1;  // binary "0" มี 0 หนึ่งตัว, 1 ศูนย์ตัว
    // ... rest of code
}

Built-in Functions (C++20 / GCC Extensions)

#include <bit>  // C++20

int countXOR10_Modern(int n) {
    int ones = std::popcount(static_cast<unsigned>(n));
    int totalBits = sizeof(int) * 8;
    // หรือนับแค่บิตที่ significant
    int zeros = 0;
    int temp = n;
    while (temp) { zeros++; temp >>= 1; }
    zeros = totalBits - ones;  // รวม leading zeros
    // หรือนับแค่ significant bits:
    int significantBits = n ? 32 - __builtin_clz(n) : 1;
    zeros = significantBits - ones;
    return ones ^ zeros;
}

// GCC/Clang builtins
int ones = __builtin_popcount(n);
int zeros = 32 - __builtin_clz(n) - ones;  // significant bits only

Complexity

• Time: O(log n) - จำนวนบิต
• Space: O(1)

สรุป

การนับบิต 0 และ 1 แล้ว XOR กัน เป็นโจทย์ bit manipulation พื้นฐาน ใน C++20 ควรใช้ std::popcount สำหรับนับ 1s ซึ่งเป็น hardware-accelerated (POPCNT instruction) บน CPU รุ่นใหม่