代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
下面是PHP中的一些东西(所有PHP整数都是32位符号,因此是31位):
function bits_population($nInteger)
{
$nPop=0;
while($nInteger)
{
$nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
$nPop++;
}
return $nPop;
}
其他回答
一个简单的算法来计算设置位的数量:
int countbits(n) {
int count = 0;
while(n != 0) {
n = n & (n-1);
count++;
}
return count;
}
以11(1011)为例,尝试手动运行该算法。它应该对你有很大帮助!
这可以在O(k)中完成,其中k是设置的比特数。
int NumberOfSetBits(int n)
{
int count = 0;
while (n){
++ count;
n = (n - 1) & n;
}
return count;
}
从Python 3.10开始,你将能够使用int.bit_count()函数,但目前,你可以自己定义这个函数。
def bit_count(integer):
return bin(integer).count("1")
你可以:
while(n){
n = n & (n-1);
count++;
}
这背后的逻辑是n-1位从n的最右边的集合位倒出来。
如果n=6,即110,那么5是101,位从n的最右边的集合位倒出来。
因此,如果我们&这两个,我们将在每次迭代中使最右边的位为0,并且总是到下一个最右边的集位。因此,计数设置位。当每一位都被设置时,最糟糕的时间复杂度将是O(log n)。
Java JDK1.5
Integer.bitCount (n);
其中n是要计算1的数。
检查,
Integer.highestOneBit(n);
Integer.lowestOneBit(n);
Integer.numberOfLeadingZeros(n);
Integer.numberOfTrailingZeros(n);
//Beginning with the value 1, rotate left 16 times
n = 1;
for (int i = 0; i < 16; i++) {
n = Integer.rotateLeft(n, 1);
System.out.println(n);
}