หาความเท่า-ต่าง (Parity) ของจำนวนอย่างมีประสิทธิภาพใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมหา Parity (ความเท่า-ต่าง) ของจำนวนอย่างมีประสิทธิภาพโดยใช้บิตเวิร์ส (bitwise operations)

Parity คืออะไร?

Parity หมายถึง จำนวนบิต 1 ในการแทนค่าบाइनนารีของจำนวนนั้น

• Even Parity: จำนวนบิต 1 เป็นเลขคู่
• Odd Parity: จำนวนบิต 1 เป็นเลขคี่

อัลกอริทึมที่มีประสิทธิภาพ (XOR + Right Shift)

แทนที่จะนับบิตทีละตัว ใช้คุณสมบัติของ XOR:

int b = n;
b = b ^ (b >> 1);
b = b ^ (b >> 2);
b = b ^ (b >> 4);
b = b ^ (b >> 8);
b = b ^ (b >> 16);

หลังจากดำเนินการเสร็จ บิตสุดท้าย (LSB) ของ b จะบอก parity:

• LSB = 0 → Even Parity
• LSB = 1 → Odd Parity

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

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

void findParity(int n) {
    int b = n;
    b = b ^ (b >> 1);
    b = b ^ (b >> 2);
    b = b ^ (b >> 4);
    b = b ^ (b >> 8);
    b = b ^ (b >> 16);
    
    if ((b & 1) == 0) {
        cout << "Even Parity" << endl;
    } else {
        cout << "Odd Parity" << endl;
    }
}

int main() {
    int n = 15;  // 1111 ในบाइनนารี = 4 บิต 1 = Even
    findParity(n);
    return 0;
}

ผลลัพธ์

Even Parity

วิธีทางเลือก (Built-in)

C++20 มี std::popcount() นับบิต 1 ได้โดยตรง:

#include <bit>
cout << (std::popcount(n) % 2 == 0 ? "Even" : "Odd") << " Parity";

สรุป

วิธี XOR+Shift คำนวณ parity ใน O(log word_size) เร็วกว่าการนับทีละบิตอย่างมาก เหมาะสำหรับระบบที่ต้องการความเร็วสูง หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ