15

UInt32在不使用查找表的情况下计算设置位的数量（即计算 1 的数量）的最快方法是什么？有没有办法算进去O(1)？

4

4 回答 4

24

bit-twiddling hacks页面有许多选项。

当然，您可以争辩说遍历所有 32 个可能的位是 O(N)，因为每次的成本都相同 :)

为简单起见，我会考虑按字节查找表的方法，或 Brian Kernighan 的巧妙想法，它迭代的次数与设置的位数一样多，我将其写为：

public static int CountBits(uint value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

如果您不喜欢填充 256 项查找表的想法，那么每 nybble 查找仍然会很快。请注意，8 个数组查找可能比 32 个简单位操作慢。

当然，在采用特别深奥的方法之前，测试应用程序的真实性能是值得的……这真的是你的瓶颈吗？

于 2012-08-29T05:56:41.443 回答
23

是以下内容的副本： how-to-implement-bitcount-using-only-bitwise-operators 或 best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer

这个问题有很多解决方案。我使用的是：

    int NumberOfSetBits(int i)
    {
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
    }
于 2012-08-29T10:28:51.943 回答
16

在 .NET Core 3.0中，x86popcnt内在函数已公开，允许您对 uint 或 uint64 执行单指令填充计数计算。

int setBits = System.Runtime.Intrinsics.X86.Popcnt.PopCount(value);

还有一个 64 位版本System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount()可以在ulong64 位 CPU 上运行时使用。

于 2019-09-15T00:30:10.573 回答
-3

这是java中获取给定数字的设置位的解决方案。

import java.util.*;

public class HelloWorld {

static int setBits(int n) {
    int count = 0;
    while(n != 0) {
        count+= ((n & 1) == 1) ? 1 : 0;
        n >>= 1;

    }
    return count;
}

 public static void main(String []args){
     Scanner sc = new Scanner(System.in);
     int n = sc.nextInt();
     System.out.println("Results: " + HelloWorld.setBits(n)); 
 }
}
于 2018-07-24T12:50:07.667 回答