我喜欢寻找最短的编码方法。我发现需要一种方法来计算以二进制表示的数字的数字总和(或数字中的 1 的数量)。我使用了位运算符并发现了这一点:
r=1;while(a&=a-1)r++;
其中 a 是数字,r 是计数。a 是给定的整数。有什么办法可以缩短/改进算法?
最短的源代码长度。
我喜欢寻找最短的编码方法。我发现需要一种方法来计算以二进制表示的数字的数字总和(或数字中的 1 的数量)。我使用了位运算符并发现了这一点:
r=1;while(a&=a-1)r++;
其中 a 是数字,r 是计数。a 是给定的整数。有什么办法可以缩短/改进算法?
最短的源代码长度。
最快的代码是生成一个查找表,以变量的值作为索引。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];
.
第二快的是生成较小的查找表,以节省 ROM。例如,对数字 0 到 15 进行 nibble-wise 查找,然后您将调用该数据类型中的每个 nibble。
请注意要求“源代码的最短长度”。胡说八道,这不是专业人士使用的指标。如果这真的是你所追求的,为了有趣或混淆,那么这个问题在 SO 上是题外话,应该在https://codegolf.stackexchange.com上提问。
您的解决方案假定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 技能,尝试编写仍然为给定问题完全定义的最小代码,但生成的代码对于尝试在更基本级别进行编程的普通读者来说价值很低.
关于您问题的主题部分,计算整数位数的最快方法:这个问题已经过深入研究,并且有几种方法可用。哪一个最快取决于许多因素:
只有仔细的基准测试才能告诉您给定的方法是否比另一种更可取,或者您是否正在尝试优化与性能无关的代码。可证明的正确性比微优化更重要。许多专家认为优化总是为时过早。
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