設定計數位,在平行
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
什麼數據類型是這數? – 2013-03-03 11:51:05
該號碼被保存爲ulong – Thomas 2013-03-03 11:51:43
只要號碼> 0,您就可以向右移動,並且每次(包括第一次輪班之前)比較號碼&(uint)0x1。或者,您可以轉換63次並使用循環展開來防止代碼中的分支。 – 2013-03-03 11:53:23