Quickest/Shortest in C/C++ 方法计算二进制中 binary/aka 个 1 的位数之和

Question

我喜欢寻找最短的编码方法。我发现需要一种方法来计算二进制表示的数字的位数之和（或数字中 1 的个数）。我使用了位运算符并发现了这个：

r=1;while(a&=a-1)r++;

其中 a 是数字，r 是计数。 a 是给定的整数。有什么办法可以缩短 this/improve 算法吗？

源代码最短。

Answer 1

最快的代码是生成一个 look-up table，以变量的值作为索引。 uint8_t 的示例：

const uint8_t NUMBER_OF_ONES [256] =
{
  0, // 0
  1, // 1
  1, // 2
  2, // 3
  1, // 4
  2, // 5
  ...
  8, // 255
};

您可以将其用作 n = NUMBER_OF_ONES[a];。

第二快的是生成较小的 look-up tables，以节省 ROM。例如 nibble-wise look-up 表示数字 0 到 15，然后您将调用数据类型中的每个半字节。

请注意，要求 "Shortest as in shortest length of source code." 是无稽之谈，这不是专业人士使用的指标。如果这确实是您想要的，为了好玩或混淆，那么问题是 off-topic 上的问题，应该在 https://codegolf.stackexchange.com 上提问。

Answer 2

您的解决方案假定 a 具有无符号类型。

然而代码不适用于 a = 0。您可以这样修复它：

r=!!a;while(a&=a-1)r++;

你可以这样削掉一个字符：

for(r=!!a;a&=a-1;r++);

但这里有一个具有相同源长度的替代解决方案：

for(r=0;a;a/=2)r+=a&1;

正如 Lundin 所提到的，代码高尔夫在 Stack Overflow 上是题外话。这是一个有趣的游戏，在尝试编写仍然针对给定问题完全定义的最小代码时，绝对可以磨练他的 C 技能，但是生成的代码对于尝试在更基础级别上编程的临时读者来说价值很低.

关于您问题的主题部分，计算整数位数的最快方法：这个问题已经被深入研究，并且有几种方法可用。哪个最快取决于很多因素：

如何编写table代码。一些处理器为此提供了 built-in 指令，编译器可能会提供一种通过内部函数或内联汇编生成它们的方法。
参数值的预期范围。如果范围很小，简单的查找 table 可能会产生最佳性能。
参数值的分布：如果几乎总是给出特定值，那么仅对其进行测试可能是最快的解决方案。
cpu具体表现：不同的算法使用不同的指令，不同cpu的相对表现可能会有所不同。

只有仔细的基准测试才能告诉您给定的方法是否优于另一种方法，或者您是否正在尝试优化性能无关的代码。可证明的正确性比 micro-optimisation 重要得多。许多专家认为优化总是为时过早。

一个有趣的 32 位整数解决方案是：

uint32_t bitcount_parallel(uint32_t v) {
    uint32_t c = v - ((v >> 1) & 0x55555555);
    c = ((c >> 2) & 0x33333333) + (c & 0x33333333);
    c = ((c >> 4) + c) & 0x0F0F0F0F;
    c = ((c >> 8) + c) & 0x00FF00FF;
    return ((c >> 16) + c) & 0x0000FFFF;
}

如果乘法很快，这里有一个可能更快的解决方案：

uint32_t bitcount_hybrid(uint32_t v) {
    v = v - ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

此处详细介绍了不同的解决方案：https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

Quickest/Shortest in C/C++ 方法计算二进制中 binary/aka 个 1 的位数之和

Quickest/Shortest in C/C++ method to calculate sum of digits in binary/aka number of 1s in binary

c

c++

binary

performance

shortest