代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
在Java 8或9中只调用Integer。bitCount。
其他回答
对于Java,有一个Java .util. bitset。 https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html
cardinality():返回在BitSet中设置为true的比特数。
BitSet是内存高效的,因为它被存储为Long类型。
// How about the following:
public int CountBits(int value)
{
int count = 0;
while (value > 0)
{
if (value & 1)
count++;
value <<= 1;
}
return count;
}
几个悬而未决的问题:-
如果这个数是负的呢? 如果这个数字是1024,那么“迭代除以2”方法将迭代10次。
我们可以修改算法以支持负数:-
count = 0
while n != 0
if ((n % 2) == 1 || (n % 2) == -1
count += 1
n /= 2
return count
现在为了克服第二个问题,我们可以编写这样的算法:-
int bit_count(int num)
{
int count=0;
while(num)
{
num=(num)&(num-1);
count++;
}
return count;
}
完整参考请参见:
http://goursaha.freeoda.com/Miscellaneous/IntegerBitCount.html
我觉得很无聊,于是对三种方法进行了十亿次迭代。编译器是gcc -O3。CPU就是第一代Macbook Pro里装的东西。
最快的是3.7秒:
static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}
第二名是相同的代码,但查找的是4个字节而不是2个半字。这花了大约5.5秒。
第三名是“横向加法”法,用时8.6秒。
第四名是GCC的__builtin_popcount(),仅为11秒。
一次一个比特的计数方法要慢得多,我厌倦了等待它完成。
因此,如果您最关心的是性能,那么请使用第一种方法。如果您关心它,但又不想在上面花费64Kb的RAM,那么可以使用第二种方法。否则,请使用可读的(但速度较慢)一次一位的方法。
很难想象在什么情况下你会想要使用比特旋转方法。
编辑:这里也有类似的结果。
你可以:
while(n){
n = n & (n-1);
count++;
}
这背后的逻辑是n-1位从n的最右边的集合位倒出来。
如果n=6,即110,那么5是101,位从n的最右边的集合位倒出来。
因此,如果我们&这两个,我们将在每次迭代中使最右边的位为0,并且总是到下一个最右边的集位。因此,计数设置位。当每一位都被设置时,最糟糕的时间复杂度将是O(log n)。