パリティについて
概要
- 誤り訂正符号の一つ
- 様々な流儀があるが、基本はデータのすべての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), "一致しませんでした"