我喜欢寻找最短的编码方法。我发现需要一种方法来计算以二进制表示的数字的数字总和(或数字中 1 的数量)。我使用了位运算符并发现了这个:
r=1;while(a&=a-1)r++;
其中 a 是数字,r 是计数。 a 是给定的整数。有什么办法可以缩短这个/改进算法吗?
最短的源代码长度。
最佳答案
您的解决方案假定 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 技能,尝试编写仍然完全定义给定问题的最小代码,但生成的代码对于尝试在更基础的级别进行编程的临时读者来说值(value)不大。
关于您问题的主题部分,计算整数位数的最快方法:这个问题已经被深入研究,并且有多种方法可用。哪一个最快取决于许多因素:
- 代码的可移植性如何。一些处理器为此提供了内置指令,编译器可能提供一种通过内在函数或内联汇编生成它们的方法。
- 参数的预期值范围。如果范围很小,简单的查找表可能会产生最佳性能。
- 参数值的分布:如果几乎总是给出特定值,则仅测试它可能是最快的解决方案。
- CPU具体性能:不同的算法使用不同的指令,不同CPU的相对性能可能会有所不同。
只有仔细的基准测试才能告诉您某种给定方法是否优于另一种方法,或者您是否正在尝试优化与性能无关的代码。可证明的正确性比微优化远重要。许多专家认为优化总是为时过早。
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
关于c++ - C/C++ 中最快/最短的方法来计算二进制数字之和/又称二进制中 1 的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49147623/