旅の途中。

ここは歩き始めた旅の途中

Popcount

はじめに

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.畳み込み

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演算、奥が深い(小並感)