数値のパリティを効率的に見つけるためのC++プログラム

この記事では、与えられた数Nのパリティを見つけるプログラムについて説明します。

パリティは、数値の2進表現におけるセットビットの数（「1」の数）として定義されます。

バイナリ表現の「1」の数が偶数の場合、パリティは偶数パリティと呼ばれ、バイナリ表現の「1」の数が奇数の場合、パリティは奇数パリティと呼ばれます。

指定された数がNの場合、次の操作を実行できます。

• y =N ^（N>> 1）
• y =y ^（y>> 2）
• y =y ^（y>> 4）
• y =y ^（y>> 8）
• y =y ^（y>> 16）

これらすべての操作が完了すると、yの右端のビットは数値のパリティを表します。ビットが1の場合、パリティは奇数になり、ビットが0の場合、パリティは偶数になります。

例

#include <bits/stdc++.h>
using namespace std;
bool calc_parity(int N) {
   int y;
   y= N ^ (N >> 1);
   y = y ^ (y >> 2);
   y = y ^ (y >> 4);
   y = y ^ (y >> 8);
   y = y ^ (y >> 16);
   //checking the rightmost bit
   if (y & 1)
      return 1;
   return 0;
}
int main() {
   int n=1345;
   int result = calc_parity(n);
   if(result==1)
      cout << "Odd Parity" << endl;
   else
      cout << "Even Parity" << endl;
   return 0;
}

出力

Even Parity