且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

在 O(1) 中计算数字中的位数

更新时间:2023-02-11 16:50:23

这看起来像是 Bit Twiddling Hacks

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;          // result goes here

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

"当输入均匀分布在 32 位值上时,此方法效果很好,因为 76% 的输入被第一次比较捕获,21% 被第二次比较捕获,2% 被第三次捕获,并且依此类推(每次比较将剩余的减少 90%).因此,平均需要的操作少于 2.6 次."

"This method works well when the input is uniformly distributed over 32-bit values because 76% of the inputs are caught by the first compare, 21% are caught by the second compare, 2% are caught by the third, and so on (chopping the remaining down by 90% with each comparision). As a result, less than 2.6 operations are needed on average."