とある問題の解答

unsigned char foo(unsigned char x){

  unsigned char a = x;

  a = (a & 0x55) + (a>>1 & 0x55);

  a = (a & 0x33) + (a>>2 & 0x33);

  a = (a & 0x0f) + (a>>4 & 0x0f);

  return a;

}

というのをトイレでぼやーっと考えてて思い出した。変数aを持ち出すのはスタックとレジスタの関係でこうしとくとコンパイラによる高速化が期待できるらしい*1。コードの美しさとの両天秤。
センター試験のプログラミングの問題はいい加減goto文やめてビット演算(or論理演算子)でも出すべき。ド・モルガンの公式も簡単に問題にできるし、、というかそれしか出せないけど。

同様に

int bitcount(unsigned long x){

  int c = 0;

  while (x) {

    ++c;

    x &= (x - 1);

  }

  return c;

}

と、ぐぐってたらK&Rにこんなの載ってるよって出てきたやつ、確かにこういうのもあった。どっちが早いんだろ、感覚的には与えられる変数がランダムなら上だが、下もケース次第(立ってるビットが少ないとか)では悪くないかも。ちなみに評価だけ見ればO(log2(n))とO(n)、ってもせいぜい32bitか64bitだし。

ちなみにこんなのもある

int bitcount3(unsigned long n){

    n = n - ( (n >> 1) & 033333333333) - ( (n >> 2) & 011111111111);

    return ( (n + (n >> 3) ) & 030707070707) % 077;

}

というわけで立ってるフラグの数を数える、もとい立ってるビット数を数えるアルゴリズム特集でした。

*1:コンパイラが勝手に最適化してくれそうではあるが