0

重複の可能性：64ビット（長い、大きい）整数のビット数をカウントしますか？

画像比較アルゴリズムの場合、結果として64ビットの数値が得られます。数字の1の数（ulong）（101011011100 ...）は、2つの画像がどれほど似ているかを示しているので、それらを数える必要があります。C＃でこれを行うにはどうすればよいですか？これをWinRTとWindowsPhoneアプリで使用したいので、低コストの方法も探しています。

編集：私は多数の画像のビットを数えなければならないので、lookup-table-approachが最善であるかどうか疑問に思っています。しかし、それがどのように機能するのかはよくわかりません...

4

4 に答える 4

2

SeanEronAndersonのBitTwiddlingHacksには、とりわけこのトリックがあります。

並列に設定されたカウントビット

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];

バイナリとして表されるB配列は、次のとおりです。

B[0] = 0x55555555 = 01010101 01010101 01010101 01010101
B[1] = 0x33333333 = 00110011 00110011 00110011 00110011
B[2] = 0x0F0F0F0F = 00001111 00001111 00001111 00001111
B[3] = 0x00FF00FF = 00000000 11111111 00000000 11111111
B[4] = 0x0000FFFF = 00000000 00000000 11111111 11111111

2進マジックナンバーBとSのパターンを続行することで、より大きな整数サイズのメソッドを調整できます。kビットがある場合、配列SとBはceil（lg（k））要素の長さである必要があります。そして、SまたはBが長いのと同じ数のcの式を計算する必要があります。32ビットvの場合、16の操作が使用されます。32ビット整数vのビットをカウントするための最良の方法は次のとおりです。

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

最良のビットカウント方法は、ルックアップテーブル方法と同じ12の操作のみを実行しますが、テーブルのメモリと潜在的なキャッシュミスを回避します。これは、上記の純粋な並列方式と、64ビット命令を使用しないものの、乗算を使用する以前の方式（64ビット命令でビットをカウントするセクション）のハイブリッドです。バイトに設定されたビットのカウントは並行して行われ、バイトに設定されたビットの合計は、0x1010101を掛けて右に24ビットシフトすることによって計算されます。

128までのビット幅の整数（タイプTでパラメーター化）への最良のビットカウント方法の一般化は次のとおりです。

v = v - ((v >> 1) & (T)~(T)0/3);                           // temp
v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3);      // temp
v = (v + (v >> 4)) & (T)~(T)0/255*15;                      // temp
c = (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * CHAR_BIT; // count
于 2013-03-03T11:57:50.030 に答える
1

これらの行に沿って何かが行われます（これはテストされたコードではないことに注意してください。私はここに書いただけなので、微調整が必​​要になる可能性があります）。

int numberOfOnes = 0;
for (int i = 63; i >= 0; i--)
{
    if ((yourUInt64 >> i) & 1 == 1) numberOfOnes++;
    else continue;
}
于 2013-03-03T11:54:28.243 に答える
0

オプション1-64ビットの結果が2^63未満の場合、反復回数が少なくなります。

byte numOfOnes;
while (result != 0)
{
    numOfOnes += (result & 0x1);
    result = (result >> 1);
}

return numOfOnes;

オプション2-一定数の相互作用-ループ展開を使用できます：

byte NumOfOnes;

for (int i = 0; i < 64; i++)
{
    numOfOnes += (result & 0x1);
    result = (result >> 1);
}
于 2013-03-03T12:00:46.983 に答える
-1

これはBitCountの32ビットバージョンです。32ビットシフトをもう1つ追加することで、これを64ビットバージョンに簡単に拡張でき、非常に効率的です。

int bitCount(int x) {
/* first let res = x&0xAAAAAAAA >> 1 + x&55555555
 * after that the (2k)th and (2k+1)th bits of the res
 * will be the number of 1s that contained by the (2k)th 
 * and (2k+1)th bits of x
 * we can use a similar way to caculate the number of 1s
 * that contained by the (4k)th and (4k+1)th and (4k+2)th 
 * and (4k+3)th bits of x, so as 8, 16, 32
 */ 
    int varA = (85 << 8) | 85;
    varA = (varA << 16) | varA;
    int res = ((x>>1) & varA) + (x & varA);

    varA = (51 << 8) | 51;
    varA = (varA << 16) | varA;
    res = ((res>>2) & varA) + (res & varA);

    varA = (15 << 8) | 15;
    varA = (varA << 16) | varA;
    res = ((res>>4) & varA) + (res & varA);

    varA = (255 << 16) | 255;
    res = ((res>>8) & varA) + (res & varA);

    varA = (255 << 8) | 255;
    res = ((res>>16) & varA) + (res & varA);
    return res;
}
于 2013-03-03T12:00:28.840 に答える