ピットを数えないでパリティを求める

　PS/2キーボードのデータはoddパリティで保護されている。そのあたりのソース読んでいたら下位ビットから順に数えていた。確かに間違いないけど、大昔FM-7で遊んでて思いついた方法はループを使わなかった。ということで思い出しながら書いてみた。

　まず整理。パリティはデータのビットの数を数えて、奇数個か偶数個か判断する。evenパリティビットはデータの1が立っているビットの個数と足したら偶数個になるよう1/0を立てる。oddパリティビットはその逆。
http://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AA%E3%83%86%E3%82%A3%E3%83%93%E3%83%83%E3%83%88

　と、Wikipediaを探したらそのものズバリがあった。あー。
https://groups.google.com/group/comp.lang.c/msg/e65b8577d041435b?hl=en&&pli=1

せっかくなので貼っておく。右シフトしてXOR、を繰り返すことで全bitのXORを求められる。
※シフト量が4,2,1になるよう差し替えました。

#include <stdio.h>

int even_parity_xor(unsigned int a) {
  unsigned int b;
  b=a>>4; //
  a=a^b;  // 76543210 XOR xxxx7654 -> xxxx_(7^3)(6^2)(5^1)(4^0)
  b=a>>2; //
  a=a^b;  // (7^3)(6^2)(5^1)(4^0) XOR xx_(7^3)(6^2) ->xx_ (7^3^5^1)(6^2^4^0)
  b=a>>1; //
  a=a^b;  // (7^6^5^4^3^2^1^0)
  return a & 1;
}

int even_parity(unsigned int val) {
  int i, count = 0;  // start with 0 for even parity
  for (i=0; i<8; i++) {
    if (val&1) count++;
    val = val>>1;
  }
  return count & 1; // bottom bit of count is parity bit
}

main() {
  int i;
  for(i=0;i<=255;i++) {
    printf("%d L,X %d %d\n",i,even_parity(i),even_parity_xor(i));
  }
}

　なお、80系だったらコンディションコード見ればすぐにわかる。

あと、ここ面白い。
http://graphics.stanford.edu/~seander/bithacks.html