<分区>
我了解到汉明权重算法和 popcnt 可以有效地计算一个值中设置的位数。但是是否有类似的操作来计算位集的索引？例如:
0010110
将返回 7(索引 1、2 和 4 集合)
明确地说，我正在寻找尽可能低级别的实现。 我的目标是对长度最大为 1024 位的值执行此操作。
<分区>
我了解到汉明权重算法和 popcnt 可以有效地计算一个值中设置的位数。但是是否有类似的操作来计算位集的索引？例如:
0010110
将返回 7(索引 1、2 和 4 集合)
明确地说，我正在寻找尽可能低级别的实现。 我的目标是对长度最大为 1024 位的值执行此操作。
最佳答案
如果您希望快速实现，我建议使用包含 256 个条目的查找表，为所有可能的字节值提供所需的总和(因为最大总和为 28，这将适合一个字节)。
然后以字节为单位拆分整数(我不知道有多少，你没有指定)并累积查找的值。
为了获得正确的总数，您必须针对每个字节的索引来源进行调整。两种选择
为不同的字节实现单独的表，
还使用位计数表来计算校正(8 x 字节索引 x 位计数)。
.
unsigned char Byte0Sum[256]= { 0, 0, 1, 1, 2, 2, 3, 3, ... };
unsigned char Byte1Sum[256]= { 0, 8, 9, 17, 10, 18, 19, 27, ... };
...
unsigned Total= ByteSum0[N & 255] + ByteSum1[(N >> 8) & 255] + ...;
或
unsigned char ByteCount[256]= { 0, 1, 1, 2, 1, 2, 2, 3, ... };
unsigned char ByteSum[256]= { 0, 0, 1, 1, 2, 2, 3, 3, ... };
...
unsigned Total= ByteSum[N & 255] + ByteSum[(N >> 8) & 255] + 8 * ByteCount[(N >> 8) & 255] + ...;
根据您的应用，其他表格大小也可以。
关于c - 如何有效地计算 bigint 值中设置位的索引？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46275415/