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

00000111

设置了三个比特。

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


当前回答

你可以这样做:

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

工作原理如下:

首先,所有的偶数位都向右移动,并与奇数位相加,以计算两组位的数量。 然后我们两人一组,然后四个人,以此类推。

其他回答

对于Java,有一个Java .util. bitset。 https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html

cardinality():返回在BitSet中设置为true的比特数。

BitSet是内存高效的,因为它被存储为Long类型。

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;
}

另一个汉明权重算法,如果你使用的是BMI2 CPU:

the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));

c++ 20 std:: popcount

以下建议已合并http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html,并应将其添加到<bit>头。

我希望用法是这样的:

#include <bit>
#include <iostream>

int main() {
    std::cout << std::popcount(0x55) << std::endl;
}

当支持GCC时,我会尝试一下,GCC 9.1.0带有g++-9 -std=c++2a仍然不支持它。

提案说:

标题:< > 命名空间STD { // 25.5.6,计数 模板类T > < conexpr int popcount(T x) noexcept;

and:

模板类T > < conexpr int popcount(T x) noexcept; 约束:T是无符号整数类型(3.9.1 [basic.fundamental])。 返回:x值中的1位数。

std::rotl和std::rotr也被添加来执行循环位旋转:c++中循环移位(旋转)操作的最佳实践

从Python 3.10开始,你将能够使用int.bit_count()函数,但目前,你可以自己定义这个函数。

def bit_count(integer):
    return bin(integer).count("1")