代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
我特别喜欢这个来自《财富》的例子:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255) #define BX_(x) ((x) - (((x)>>1)&0x77777777) - (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
我最喜欢它,因为它太漂亮了!
其他回答
32位还是32位?我只是在阅读了“破解编码面试”第4版练习5.5(第5章:位操作)后,在Java中使用了这种方法。如果最小有效位是1个增量计数,则右移该整数。
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
我认为这个比常数0x33333333的解更直观,不管它们有多快。这取决于你对“最佳算法”的定义。
你可以这样做:
int countSetBits(int n)
{
n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);
n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);
n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);
n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);
return n;
}
int main()
{
int n=10;
printf("Number of set bits: %d",countSetBits(n));
return 0;
}
海王: http://ideone.com/JhwcX
工作原理如下:
首先,所有的偶数位都向右移动,并与奇数位相加,以计算两组位的数量。 然后我们两人一组,然后四个人,以此类推。
另一个汉明权重算法,如果你使用的是BMI2 CPU:
the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));
private int get_bits_set(int v)
{
int c; // 'c' accumulates the total bits set in 'v'
for (c = 0; v>0; c++)
{
v &= v - 1; // Clear the least significant bit set
}
return c;
}
int countBits(int x)
{
int n = 0;
if (x) do n++;
while(x=x&(x-1));
return n;
}
或者:
int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }
在我最初的回答7年半之后,@PeterMortensen质疑这是否是有效的C语法。我发布了一个在线编译器的链接,显示它实际上是完全有效的语法(代码如下)。
#include <stdio.h>
int countBits(int x)
{
int n = 0;
if (x) do n++; /* Totally Normal Valid code. */
while(x=x&(x-1)); /* Nothing to see here. */
return n;
}
int main(void) {
printf("%d\n", countBits(25));
return 0;
}
输出:
3
如果你想重新写清楚,它看起来是这样的:
if (x)
{
do
{
n++;
} while(x=x&(x-1));
}
但在我看来,这太过分了。
然而,我也意识到函数可以变得更短,但可能更神秘,写为:
int countBits(int x)
{
int n = 0;
while (x) x=(n++,x&(x-1));
return n;
}