1

これは事実上対数ベース 2 ですが、私がいる環境ではこの機能にアクセスできません。ビットを手動で調べて確認するのは容認できないほど遅いです。わずか 4 ビットの場合は、おそらくインデックスを付けて配列内のスペースを無駄にすることができますが、64 ビットでは実行できません。

どのビットが設定されているかを見つけるための巧妙な一定時間の方法はありますか? (数量は 64 ビットの数値です)。

編集: 明確にするために、番号に 1 つのビットが設定されています。

4

4 に答える 4

0

数値が 2 の累乗で、ビット カウント命令がある場合は、次のように実行できます。

bitcount(x-1)

例えば

  x      x-1     bitcount(x-1)  

  b100   b011    2  
  b001   b000    0

数値が 2 の累乗でない場合、これは機能しないことに注意してください。

編集

De Brujin メソッドの 64 ビット版は次のとおりです。

static const int log2_table[64] = {0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 
                                   20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31,
                                   35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 
                                   33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 
                                   23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58};

int fastlog2(unsigned long long x) {
    return log2_table[ ( x * 0x218a392cd3d5dbfULL ) >> 58 ];
}

テストコード:

int main(int argc,char *argv[])
{
    int i;
    for(i=0;i<64;i++) {
        unsigned long long x=1ULL<<i;
        printf("0x%llu -> %d\n",x,fastlog2(x));
    }
    return 0;
}

魔法の 64 ビット数は、次数 6 のバイナリ De Brujin シーケンスです。

2 の累乗を掛けることは、この数を特定の桁数だけシフトすることと同じです。

これは、乗算結果の上位 6 ビットが、各入力数値の異なる 6 桁のサブシーケンスに対応することを意味します。De Brujin シーケンスには、各サブシーケンスが一意であるというプロパティがあるため、適切なルックアップ テーブルを構築して、サブシーケンスからセット ビットの位置に戻ることができます。

于 2013-08-21T18:44:48.223 に答える
0

最新の Intel CPU を使用している場合は、ハードウェアでサポートされている "POPulation CouNT" アセンブリ命令を使用できます。

http://en.wikipedia.org/wiki/SSE4#POPCNT_and_LZCNT

Unix/gcc の場合、マクロを使用できます。

#include <smmintrin.h>
uint64_t x;
int c = _mm_popcnt_u64(x);
于 2013-08-24T01:19:16.007 に答える