効率の良いパリティ計算方法

通信系のプログラムを書いていると、誤り検出のためにパリティビットを使用することがあります。
この記事ではuint32_t型の数値が与えられたときに、そのパリティを計算する関数を効率化することを紹介します。

関数の仕様

関数の仕様を以下のように決めます。

入力

uint32_t型の整数

出力

入力された整数を2進数で表現したときに、ビット1の数が偶数ならば0、奇数ならば1

とりあえず愚直に実装

とりあえずは、仕様を愚直に実装してみます。
32回のループを回して、1の数を数え上げています。

int parity(uint32_t val) {
  int count = 0;
  
  for(int i = 0; i < 32; i++) {
    if(val & 0x00000001) count++;
    val <<= 1;
  }
  
  return count & 0x00000001;
}

XORを使って高速化

パリティービットの生成回路をハードウェアで作るときにはXORゲートを利用します。
それを思い出して、以下のような関数にしました。
すべてのビットのXORをとり、最終的にはvalの最下位ビットにその値を入れています。

int parity(uint32_t val) {
  val ^= val >> 16;
  val ^= val >> 8;
  val ^= val >> 4;
  val ^= val >> 2;
  val ^= val >> 1;
  
  return val & 0x00000001;
}