Kiểm tra chẵn lẻ bit (Parity Check)

Giới thiệu

Chẵn lẻ (Parity) của một số dựa trên số lượng bit 1 có mặt trong biểu diễn nhị phân của số đó. Khi số lượng 1 hiện tại là lẻ, nó trả về chẵn lẻ (odd parity), cho số chẵn các 1 nó trả về chẵn (even parity).

Vì ta biết rằng các số trong bộ nhớ máy tính được lưu trữ dưới dạng số nhị phân, nên ta có thể dịch chuyển các bit dễ dàng. Trong trường hợp này, bằng cách dịch bit, ta sẽ đếm số lượng 1 có mặt trong biểu diễn nhị phân của số cho trước.

Đầu vào và Đầu ra

Đầu vào: Một số: 5. Dạng nhị phân là (101)
Đầu ra: Chẵn lẻ của 5 là Lẻ (Odd).

Thuật toán

finParity(n)
Đầu vào: Số n.
Đầu ra: Kiểm tra số có chẵn lẻ (parity) chẵn hay lẻ.

Begin
    count := 0
    temp := n
    while temp >= 2, do
        if temp có 1 là LSB, then
            count := count + 1
        temp := dịch phải temp 1 bit
    done
    if count là số lẻ, then
        hiển thị là chẵn lẻ (odd parity)
    else
        hiển thị chẵn (even parity)
End

Ví dụ (C++)

#include <iostream>
using namespace std;

bool findParity(int n) {
    int count = 0;
    int temp = n;
    while (temp >= 2) {
        if(temp & 1)  // khi LSB là 1, tăng count
            count++;
        temp = temp >> 1;  // dịch phải số 1 bit
    }
    return (count % 2) ? true : false;
}

int main() {
    int n;
    cout << "Enter a number: "; cin >> n;
    cout << "Parity of " << n << " is " << (findParity(n) ? "Odd" : "Even");
}

Kết quả

Enter a number: 5
Parity of 5 is Odd