Popcount
はじめに
- Wavelet-Treeを実装しようとした。そのために完備辞書(簡潔ビットベクトル)を実装する必要があった。そのために「立っているbit数を高速に求める関数」を書く必要があった。ので色々調べてみた。
- とても参考になったサイト
- 技術的な投稿のtestも兼ねている
- 表記方法
typedef unsigned long long u64int; //符号なし64bit整数,こいつの立っているbit数を求める u64int x; //bit countを返す関数(たかだか64なのでintで十分) int popcnt(u64int);
- お気持ちはコード中にコメントアウトした
1.愚直
int popcnt(u64int x) { int cnt = 0; while(x) cnt+=x&1, x>>=1; return cnt; }
時間計算量O(log(x))
.
2.メモリで殴る
int mp[1<<64]; void prepro(void) { for (u64int i = 0; i < (1<<64); i++) { u64int x = i, cnt = 0; while(x) cnt+=x&1, x>>=1; mp[i] = cnt; } } int popcnt(u64int x) { return mp[x]; }
時間計算量O(1)
,空間計算量O(x)
(無理).
3.畳み込み
- wiki(Efficient_implementation)
- 畳み込みという言い方があってるかどうかは定かではない
int popcnt(u64int x) { //0x5555555555555555 = 0b01010101... //2bitに纏める x = (x&0x5555555555555555) + ((x>>1)&0x5555555555555555); //0x3333333333333333 = 0b00110011... //4bitに纏める x = (x&0x3333333333333333) + ((x>>2)&0x3333333333333333); //8bitに纏める x = (x&0x0f0f0f0f0f0f0f0f) + ((x>>4)&0x0f0f0f0f0f0f0f0f); //16bit x = (x&0x00ff00ff00ff00ff) + ((x>>8)&0x00ff00ff00ff00ff); //32bit x = (x&0x0000ffff0000ffff) + ((x>>16)&0x0000ffff0000ffff); //64bit x = (x&0x00000000ffffffff) + ((x>>32)&0x00000000ffffffff); return x; }
時間・空間計算量O(log(log(x)))
.以下同様.
4.畳み込み8bit積
- 出典
- 以下のコードでは最後にshiftしている
int popcnt(u64int x) { //&演算してからshift x = (x & 0x5555555555555555ULL) + ((x & 0xAAAAAAAAAAAAAAAAULL)>>1); x = (x & 0x3333333333333333ULL) + ((x & 0xCCCCCCCCCCCCCCCCULL)>>2); x = (x & 0x0F0F0F0F0F0F0F0FULL) + ((x & 0xF0F0F0F0F0F0F0F0ULL)>>4); //8bitまで纏めれば結果は64以下なので収まる //x = x<<56 + x<<48 + ... + x<<8 + x<<0 //の上位8bitに結果が入っている x *= 0x0101010101010101ULL; return x >> 56; }
5.畳み込み8bit積ちょい高速化
int popcnt(u64int x) { /* x = 0b00 -> x>>1 == 0, x - x>>1 == 0 x = 0b01 -> x>>1 == 0, x - x>>1 == 1 x = 0b10 -> x>>1 == 1, x - x>>1 == 1 x = 0b11 -> x>>1 == 1, x - x>>1 == 2 よって (x&0x5555555555555555) + (x>>1&0x5555555555555555) = x-((x>>1)&0x5555555555555555ULL) */ x -= ((x>>1)&0x5555555555555555ULL); x = (x&0x3333333333333333ULL) + ((x&0xCCCCCCCCCCCCCCCCULL)>>2); x = (x&0x0F0F0F0F0F0F0F0FULL) + ((x&0xF0F0F0F0F0F0F0F0ULL)>>4); x *= 0x0101010101010101ULL; return x >> 56; }
おわりに
- Qiitaに書くまでもないな、と思ったらここに書いていこうかなというお気持ち
- 疑問、指摘等あればコメントまたはtwitterによろしくお願いします
- bit演算、奥が深い(小並感)