代表数字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;
}
其他回答
我觉得很无聊,于是对三种方法进行了十亿次迭代。编译器是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,那么可以使用第二种方法。否则,请使用可读的(但速度较慢)一次一位的方法。
很难想象在什么情况下你会想要使用比特旋转方法。
编辑:这里也有类似的结果。
Kotlin 1.4 之前
fun NumberOfSetBits(i: Int): Int {
var i = i
i -= (i ushr 1 and 0x55555555)
i = (i and 0x33333333) + (i ushr 2 and 0x33333333)
return (i + (i ushr 4) and 0x0F0F0F0F) * 0x01010101 ushr 24
}
这或多或少是上面那个答案的翻版。
它带有Java补丁,然后使用IntelliJ IDEA Community Edition中的转换器进行转换
1.4及以上(截至2021-05-05 -未来可能会改变)。
fun NumberOfSetBits(i: Int): Int {
return i.countOneBits()
}
在底层,它使用Integer。bitCount如下所示:
@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
@kotlin.internal.InlineOnly
public actual inline fun Int.countOneBits(): Int = Integer.bitCount(this)
下面是功能优等递归解决方案,它是迄今为止最纯粹的一个(并且可以用于任何位长度!):
template<typename T>
int popcnt(T n)
{
if (n>0)
return n&1 + popcnt(n>>1);
return 0;
}
这是在golang中的实现
func CountBitSet(n int) int {
count := 0
for n > 0 {
count += n & 1
n >>= 1
}
return count
}
对于Java,有一个Java .util. bitset。 https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html
cardinality():返回在BitSet中设置为true的比特数。
BitSet是内存高效的,因为它被存储为Long类型。