パリティ

/

パリティについて

タグ パリティ parity

概要

  • 誤り訂正符号の一つ
  • 様々な流儀があるが、基本はデータのすべてのbitのxorを計算して得られる値
  • 誤りが含まれるとパリティが一致しなくなることでエラーチェックに用いる

計算

  • \([1, 0, 0, 1]\)というビット列がある時, 1 ^ 0 ^ 0 ^ 1を計算すること

実装

  • わかりやすい方法と効率的な方法の2つを例示する
from tqdm.auto import tqdm

def calc_parity_easy(n):
    (*input,) = map(int, format(n, "b"))
    parity = 0
    for b in reversed(input):
        parity ^= int(b)
    return parity


def calc_parity_fast(n):
    parity = 0
    while n != 0:
        # 最も下のbitのフラグを抽出
        if n & 1 == 1:
            parity ^= 1
        else:
            parity ^= 0
        # 右にシフト(最下位のbitを捨てる)
        n >>= 1
    return parity


for i in tqdm(range(10 ** 6)):
    assert calc_parity_easy(i) == calc_parity_fast(i), "一致しませんでした"

参考