如何在不使用查找表情况下，最快地计算一个 UInt32 中设置为1的位数（即计算1的数量）？是否有一种可以在 O(1) 的时间内进行计数的方法？
6个回答
28
这个位运算技巧页面提供了多种解决方案。
当然，你可以争论对所有32个可能的位进行迭代是 O(N)，因为每次的成本都相同 :)
为了简单起见，我会考虑每字节查找表的方法，或者是Brian Kernighan的巧妙想法，该想法迭代与设置的位数相同次数，我的写法如下：
public static int CountBits(uint value)
{
int count = 0;
while (value != 0)
{
count++;
value &= value - 1;
}
return count;
}
如果您不喜欢填充256个条目的查找表的想法，每半字节进行一次查找仍然非常快。请注意，8个数组查找可能比32个简单位操作慢。
当然，在采用特别深奥的方法之前，测试您的应用程序的实际性能是值得的...这对您来说真的是瓶颈吗？
- Jon Skeet
4
这看起来更易读了，但我仍然想知道像这样计算位数的用途是什么。如果我不得不猜测，我会说它可能用于密码学。 - Alisson Reinaldo Silva
我对LUT方法很感兴趣。对于人口统计，特别是如果有内在的话，它似乎肯定会更慢，但是对于获取集合位的索引，如果注意一些细节，LUT似乎更快。如果您想看一下，我已经在GitHub上探索了这个问题。 - Polynomial
在我的情况下，我需要计算给定子网掩码中有多少个IP地址：
var power = IPAddress.Parse("255.255.240.0").GetAddressBytes().Select(b => b.InverseBits()).CountSetBits(); var addressesInNetwork = Math.Pow(2, power); - Janis Veinbergs@AlissonReinaldoSilva：我使用这个函数来检查一个数字是否是2的正整数次幂，这是一个比较特殊的情况；即
var isPowerOf2 = (CountBits(input) == 1 && input>0);。 - to11mtm26
这是一个重复的问题： 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;
}
- Manuel Amstutz
2
2我测试了这个答案和Jon Skeet的答案的性能。虽然那种方法更易读，但这个方法是最快的。 - raoul
@raoul：虽然这对于每种情况都具有相同的性能（包括一个乘法的12个算术运算），但如果只设置了少量位（这是枚举类型的典型情况），Jon的版本（实际上是Brian Kerninghan的版本）可能会更快。 - György Kőszeg
22
在.NET Core 3.0中，x86
popcnt内部函数已经暴露出来，允许您对uint或uint64执行单指令种群计数计算。int setBits = System.Runtime.Intrinsics.X86.Popcnt.PopCount(value);
还有一个64位版本的System.Runtime.Intrinsics.X86.Popcnt.X64.PopCount()，可以在64位CPU上使用，用于ulong。
- Polynomial
6
谢谢！您知道是否有一种内在或事实上的算法来返回集合位的索引，而不仅仅是计数吗？ - Alex Norcliffe
2@AlexNorcliffe 这在内部不可能实现。最简单的方法就是循环遍历值中的所有位，并将设置位的索引放入列表中。您可以通过提前计算popcount来进一步加快速度，这样您就可以使用预分配的数组而不是
List对象。更快的方法是像John Skeet上面提到的那样将数字拆分成块，以便您可以使用查找表。我在这里进行了调查，并显示它通常比每次计算位置要快。 - Polynomial1太好了 - 谢谢！我必须承认，我很困惑为什么HashSet对我来说表现最快，即使使用了.NET Core中2019年2月的最新参考源代码BitArray，该代码使用Span和积极内联进行优化。在我的测试中，我有500万个值和250万个次要值。我的目标是最终得到一个列表，其中第一个列表中的哪些值不在第二个列表中。它们是连续的整数，所以我期望BitArray会胜出 - 但无法理解如何调用HasSet<>.Remove可能更快！尽管它确实使用了更多的分配。 - Alex Norcliffe
1@AlexNorcliffe 我查看了BitArray的参考源代码，每个新实例都会创建一个堆分配（足够大以容纳位的Int32值数组），扩展数组（即将Length属性设置为较大的值）会导致新的分配和复制，缩小数组会导致未使用的数组元素和最终元素位被清除。对BitArray进行foreach循环也会在堆上分配一个新的枚举器对象，但Get函数应该很快：一个对齐的内存访问，一个除法，一个模数，一个变量左移，一个AND，一个整数比较。 - Polynomial
1@AlexNorcliffe 另一个潜在的选择是使用BitVector32，它实际上是一种位提取数学的封装，带有一些方便的方法，并且由于它是一个结构体，所以它被放置在堆栈上而不是堆上。但最快的性能几乎肯定总是手动在自己的代码中进行计算，全部内联，因为您可以避免进行调用和分支（大多数对框架类的调用都具有参数验证！），并保持非常紧密的循环以获得更好的性能。 - Polynomial
4@Polynomial，自从.NET Core 3.0以来，有一种更好的解决方案：BitOperations.PopCount，它可在所有平台上使用，并且（希望）使用了您提到的内置操作。 - Mark
9
在核心 3.0 及以上版本中提供了一个平台无关的BitOperations.PopCount。
当硬件内部函数可用时，它将使用硬件内部函数；否则，它将默认使用软件回退。目前支持 X86/64 和 ARM 处理器。
感谢 @Mark 在另一个答案的评论中提到此事。
- dana
1
1太好了！谢谢！ - undefined
3
根据.NET 7的情况，Int32（和其他整数类型）具有静态PopCount方法，因此您只需调用int.PopCount(int bitMask)，而无需编写自己的算法或依赖System.Numerics和带有BitOperations的无符号类型。
https://learn.microsoft.com/en-us/dotnet/api/system.int32.popcount
- Jeff Camera
-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));
}
}
- chandan gupta
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接