代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
这也可以正常工作:
int ans = 0;
while(num) {
ans += (num & 1);
num = num >> 1;
}
return ans;
其他回答
我使用下面的函数。我还没有检查基准测试,但它是有效的。
int msb(int num)
{
int m = 0;
for (int i = 16; i > 0; i = i>>1)
{
// debug(i, num, m);
if(num>>i)
{
m += i;
num>>=i;
}
}
return m;
}
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)
32位还是32位?我只是在阅读了“破解编码面试”第4版练习5.5(第5章:位操作)后,在Java中使用了这种方法。如果最小有效位是1个增量计数,则右移该整数。
public static int bitCount( int n){
int count = 0;
for (int i=n; i!=0; i = i >> 1){
count += i & 1;
}
return count;
}
我认为这个比常数0x33333333的解更直观,不管它们有多快。这取决于你对“最佳算法”的定义。
"最佳算法"是什么意思?短码还是长码?您的代码看起来非常优雅,并且具有恒定的执行时间。代码也很短。
但如果速度是主要因素,而不是代码大小,那么我认为以下方法可以更快:
static final int[] BIT_COUNT = { 0, 1, 1, ... 256 values with a bitsize of a byte ... };
static int bitCountOfByte( int value ){
return BIT_COUNT[ value & 0xFF ];
}
static int bitCountOfInt( int value ){
return bitCountOfByte( value )
+ bitCountOfByte( value >> 8 )
+ bitCountOfByte( value >> 16 )
+ bitCountOfByte( value >> 24 );
}
我认为这不会更快的64位值,但32位值可以更快。
一个简单的方法,应该工作得很好少量的比特它像这样(在这个例子中的4位):
(i & 1) + (i & 2)/2 + (i & 4)/4 + (i & 8)/8
对于少量的比特,其他人会推荐这种简单的解决方案吗?