Tìm chẵn lẻ (Parity) của số hiệu quả trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ xác định parity (chẵn/lẻ) của một số nguyên bằng cách dùng các phép toán bitwise XOR và dịch phải (right-shift) - phương pháp hiệu quả O(1) không cần đếm bit.

Thuật toán

Áp dụng chuỗi phép toán:

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

Bit cuối cùng (LSB) của b: 0 → chẵn (Even Parity), 1 → lẻ (Odd Parity).

Mã nguồn ví dụ

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

void findParity(int n) {
    int b;
    b = n ^ (n >> 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 bit 1 → chẵn
    findParity(n);
    return 0;
}

Kết quả đầu ra

Even Parity

Giải thích

15 = 1111₂ có 4 bit 1 → parity chẵn. Thuật toán gom toàn bộ bit về LSB bằng cách XOR liên tiếp các nửa.

Kết luận

Phương pháp bitwise cực nhanh, phù hợp cho hệ thống nhúng, truyền thông. Nếu bạn có thắc mắc, hãy để lại bình luận bên dưới.