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

Parity (Độ chẵn/lẻ) – Số lượng bit 1 trong biểu diễn nhị phân. Chẵn = even parity, Lẻ = odd parity.

Thuật toán XOR gộp bit (O(1) trên 32-bit)

y = n ^ (n >> 1);
y = y ^ (y >> 2);
y = y ^ (y >> 4);
y = y ^ (y >> 8);
y = y ^ (y >> 16);
// Bit cuối cùng (LSB) của y là parity: 1=odd, 0=even

Chương trình C++

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

bool getParity(int n) {
    int y = n;
    y ^= y >> 1;
    y ^= y >> 2;
    y ^= y >> 4;
    y ^= y >> 8;
    y ^= y >> 16;
    return y & 1; // 1 = odd parity, 0 = even parity
}

int main() {
    int nums[] = {1345, 7, 10, 0, 255};
    for (int n : nums) {
        cout << n << " (binary: " << bitset<16>(n) << ") -> "
             << (getParity(n) ? "Odd Parity" : "Even Parity") << "\n";
    }
    return 0;
}

Kết quả

1345 (binary: 0000010100111001) -> Even Parity
7 (binary: 0000000000000111) -> Odd Parity
10 (binary: 0000000000001010) -> Even Parity
0 (binary: 0000000000000000) -> Even Parity
255 (binary: 0000000011111111) -> Even Parity

Lưu ý

• Trên C++20: dùng std::popcount(n) % 2.
• GCC/Clang builtin: __builtin_parity(n).