ビット演算備忘録はじまめした。

Cゴルフやってると変なビット演算の使い方がよく出てくるので備忘録作っとく。
たまに普通のプログラミングにも使えるテクニックが出てくる、はず。

・nCk mod 2 はANDで書ける。
http://golf.shinh.org/p.rb?Half+Sierpinski

nnさんが詳しい解説をしているのでここでは省略。

・ビットカウント
高速化について。これは実践的な話。

int bitcount(int i) {
　　i = (i & 0x55555555) + (i >> 1 & 0x55555555);
　　i = (i & 0x33333333) + (i >> 2 & 0x33333333);
　　i = (i & 0x0f0f0f0f) + (i >> 4 & 0x0f0f0f0f);
　　i = (i & 0x00ff00ff) + (i >> 8 & 0x00ff00ff);
　　return (i & 0x0000ffff) + i;
}

これは割と有名。
最後の２行はreturn i * 0x01010101 >> 24;でもよい。
立っているビットの数が少ないことが分かっているときは下のようにすればいい。

int bitcount(int i) {
　　int num;
　　for(num = 0; i; i &= i-1) num++;
　　return num;
}