如何从64位数字中获得1s的数量 [英] How to get amount of 1s from 64 bit number

问题描述

可能的重复项:计算64位(长，大)中的位数 整数?

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

对于图像比较算法，我得到一个64位数字.数字(ulong)中的1s(101011011100 ...)告诉我两个图像的相似程度，因此我需要对它们进行计数.我将如何在C#中做到最好? 我想在WinRT& Windows Phone App，所以我也在寻找一种低成本的方法.

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.

由于我必须计算大量图像的位数，所以我想知道lookup-table-approach是否是最好的方法.但我不确定这是如何工作的...

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...

推荐答案

Sean Eron安德森(Anderson)的Bit Twiddling Hacks 具有以下技巧:

并行设置计数位

Counting bits set, in parallel

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数组是:

The B array, expressed as binary, is:

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中位的最佳方法如下:

We can adjust the method for larger integer sizes by continuing with the patterns for the Binary Magic Numbers, B and S. If there are k bits, then we need the arrays S and B to be ceil(lg(k)) elements long, and we must compute the same number of expressions for c as S or B are long. For a 32-bit v, 16 operations are used. The best method for counting bits in a 32-bit integer v is the following:

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位来计算的.

The best bit counting method takes only 12 operations, which is the same as the lookup-table method, but avoids the memory and potential cache misses of a table. It is a hybrid between the purely parallel method above and the earlier methods using multiplies (in the section on counting bits with 64-bit instructions), though it doesn't use 64-bit instructions. The counts of bits set in the bytes is done in parallel, and the sum total of the bits set in the bytes is computed by multiplying by 0x1010101 and shifting right 24 bits.

将最佳位计数方法推广到位宽最大为128(由T型参数化)的整数是这样的:

A generalization of the best bit counting method to integers of bit-widths upto 128 (parameterized by type T) is this:

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

这篇关于如何从64位数字中获得1s的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！