0

Possible duplicate: Count number of bits in a 64-bit (long, big) integer?

For an image comparison algorithm I get a 64bit number as result. The amount of 1s in the number (ulong) (101011011100...) tells me how similar two images are, so I need to count them. How would I best do this in C#? I'd like to use this in a WinRT & Windows Phone App, so I'm also looking for a low-cost method.

EDIT: As I have to count the bits for a large number of Images, I'm wondering if the lookup-table-approach might be best. But I'm not really sure how that works...

4

4 回答 4

2

Sean Eron Anderson的Bit Twiddling Hacks有这个技巧，其中包括：

计数位设置，并行

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

我们可以通过继续使用二进制幻数 B 和 S 的模式来调整更大整数大小的方法。如果有 k 位，那么我们需要数组 S 和 B 是 ceil(lg(k)) 个元素长，并且我们必须为 c 计算与 S 或 B 长的相同数量的表达式。对于 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

Something along these lines would do (note that this isn't tested code, I just wrote it here, so it may and probably will require tweaking).

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 位轻松地将其扩展到 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 回答