計數只用按位運算

Question

設置的位數

可能重複：
Best algorithm to count the number of set bits in a 32-bit integer?

僅使用！ 〜&^| + < < >>運算符，我需要計數在32位整數中設置的位數，而只能直接訪問8位。所以只有0xaa不是0xaaaa

Ex。 0x07 = 3和0x05 = 2

我也只能使用最多40個操作員。

現在我的解決方案採用90是：

int countBitsSet(int x) 
{ 
int count = 0; 
int mask = 0x01 // 00000001 

count = (x & mask); 
count += (x >> 1) & mask; 
count += (x >> 2) & mask; 
. 
. 
. 
count += (x >> 31) & mask; 

return count; 
} 

有誰知道的方式，以減少這一步了一半？我正在考慮找到一種方法來並行或者其他方式並且同時計數4位，但我無法弄清楚如何。其他人已經在25個運營商那裏做過，所以我知道有一種方法。有任何想法嗎？

Answer 1

1）你計算錯誤的結果; 31的轉變缺失。 2）你應該使用for循環。 3）搜索位計數算法會給你一堆鏈接。