variable-precision SWARアルゴリズムの紹介

1923 ワード

BITCOUNTコマンドは、1つのビット配列の0進数以外のビットの数を統計し、数学的には「Hanmming Weight」と呼ばれます.
現在最も効率的なvariable-precision SWARアルゴリズムは,定数時間で複数バイトの非0数を計算することができ,アルゴリズム設計が非常に精巧で学習に値する.

int swar(uint32_t i)
{
    // (A)
    i = ( i & 0x55555555) + ((i >> 1) & 0x55555555);

    // (B)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

    // (C)
    i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

    // (D)
    i = (i * 0x01010101) >> 24);

    return i;
}

原理説明:
(A)0 x 555555バイナリ:0101 0101 0101 0101 0101 0101 0101 0101 0101、奇位1、偶数0
iのバイナリでb 31 b 30を表すと....... b7 b6 b5 b4 b3 b2 b1 b0
i&0 x 555555はすべての奇数ビットを取り出します:0 b 30......0 b6 0 b4 0 b2 0 b0
(i>>1)&0 x 55555555偶数位:0 b 31 0 b 7 0 b 5 0 b 3 0 b 1
両者加算:+-----------------------------------------------------------------
0 (b30+b31) ..... 0 (b6+b7) 0 (b4+b5) 0 (b2+b3) 0 (b0+b1)
原理はバイナリ2ビットの1つの分割によって、その2ビットの1の数を計算することである.

(B)(A)ステップをバイナリ2ビットで区切る1の数を4ビットで加算
(C)(B)ステップにおける1の数を8 bitビットずつ加算
(D)(C)ステップで8 bit分割の2進数を算出した
例えばbyte 3 byte 2 byte 1 byte 0
y = y3 y2 y1 y0
では、y*0 x 0100101は、y 0 y 1 y 2ビットとy 3位置の加算則yの値を以下のように実現する.
byte3 byte2 byte1 byte0
yn=y 3+y 2+y 1+y 0 x 2 x 1 x 0将yn>24ビットはy 3+y 2+y 1+y 0の効果を得た.

Wormholes--POJ 3259

ああ!アルゴリズム:復号文