代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
代表数字7的8位像这样:
00000111
设置了三个比特。
确定32位整数中设置位数的算法是什么?
当前回答
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)
其他回答
摘自《黑客的喜悦》第66页,图5-2
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
执行大约20条指令(依赖于arch),没有分支。黑客的喜悦是令人愉快的!强烈推荐。
我个人使用这个:
public static int myBitCount(long L){
int count = 0;
while (L != 0) {
count++;
L ^= L & -L;
}
return count;
}
下面是示例代码,可能很有用。
private static final int[] bitCountArr = new int[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
private static final int firstByteFF = 255;
public static final int getCountOfSetBits(int value){
int count = 0;
for(int i=0;i<4;i++){
if(value == 0) break;
count += bitCountArr[value & firstByteFF];
value >>>= 8;
}
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
我使用下面更直观的代码。
int countSetBits(int n) {
return !n ? 0 : 1 + countSetBits(n & (n-1));
}
逻辑:n & (n-1)重置n的最后一个集合位。
附注:我知道这不是O(1)解,尽管这是一个有趣的解。