2013-03-03 53 views
0

可能重複:Count number of bits in a 64-bit (long, big) integer?如何獲得1秒的量從64位數字

對於圖像比較算法我得到一個64位數字的結果。數量(ulong)(101011011100 ...)中的1表示告訴我兩張圖像有多相似,所以我需要對它們進行計數。我如何最好地在C#中做到這一點? 我想在WinRT中&的Windows Phone應用程序使用這個,所以我也在尋找一種低成本的方法。

編輯:正如我都數不過來了位了大量的圖片,我想知道如果查找表的方法可能是最好的。但我真的不知道如何工作的?

+0

什麼數據類型是這數? – 2013-03-03 11:51:05

+0

該號碼被保存爲ulong – Thomas 2013-03-03 11:51:43

+0

只要號碼> 0,您就可以向右移動,並且每次(包括第一次輪班之前)比較號碼&(uint)0x1。或者,您可以轉換63次並使用循環展開來防止代碼中的分支。 – 2013-03-03 11:53:23

回答

2

Sean Eron Anderson's 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是小區(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 
+0

哇,這看起來相當複雜。你能向我解釋究竟發生了什麼嗎?另外這個必須修改爲ulong,doens't它? – Thomas 2013-03-03 12:27:33

1

東西沿着這些路線會做(注意,這是沒有經過測試的代碼,我只是寫在這裏,因此它可能和可能需要的調整)。

int numberOfOnes = 0; 
for (int i = 63; i >= 0; i--) 
{ 
    if ((yourUInt64 >> i) & 1 == 1) numberOfOnes++; 
    else continue; 
} 
0

這是比特計數的一個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; 
} 
0

選項1 - 如果64位結果較少迭代< 2^63:

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

return numOfOnes; 

選項2 - interations的恆定數目的 - 都可以使用循環展開:

byte NumOfOnes; 

for (int i = 0; i < 64; i++) 
{ 
    numOfOnes += (result & 0x1); 
    result = (result >> 1); 
} 
相關問題