代表数字7的8位像这样:

00000111

设置了三个比特。

确定32位整数中设置位数的算法是什么?


当前回答

将整数转换为二进制字符串并计数。

PHP解决方案:

substr_count(decbin($integer), '1');

其他回答

一个简单的方法,应该工作得很好少量的比特它像这样(在这个例子中的4位):

(i & 1) + (i & 2)/2 + (i & 4)/4 + (i & 8)/8

对于少量的比特,其他人会推荐这种简单的解决方案吗?

如果你使用c++,另一个选择是使用模板元编程:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

用法如下:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

当然,你可以进一步扩展这个模板来使用不同的类型(甚至是自动检测位大小),但为了清晰起见,我让它保持简单。

edit:忘了说这很好,因为它应该在任何c++编译器中工作,它基本上只是为你展开循环,如果一个常量值用于比特计数(换句话说,我很确定这是你能找到的最快的通用方法)

对于232查找表和逐个遍历每个位之间的折中方法:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

从http://ctips.pbwiki.com/CountBits

下面是功能优等递归解决方案,它是迄今为止最纯粹的一个(并且可以用于任何位长度!):

template<typename T>
int popcnt(T n)
{
  if (n>0)
    return n&1 + popcnt(n>>1);
  return 0; 
}
#!/user/local/bin/perl


    $c=0x11BBBBAB;
     $count=0;
     $m=0x00000001;
    for($i=0;$i<32;$i++)
    {
        $f=$c & $m;
        if($f == 1)
        {
            $count++;
        }
        $c=$c >> 1;
    }
    printf("%d",$count);

ive done it through a perl script. the number taken is $c=0x11BBBBAB   
B=3 1s   
A=2 1s   
so in total  
1+1+3+3+3+2+3+3=19