获取整数最高十进制数的最快方法是什么？

Question

什么是最快的实施方式

template <typename T>
unsigned highest_decimal_digit(T x);

(返回例如3表示356431,7表示71表示,9表示9表示)？

我能想到的最好的是:

• constexpr-计算适合T的"中等大小"10的幂.
• 执行二进制搜索(超过10的幂,可能使用constexpr构造的查找表)来找到p,10的最高功率低于x.
• 返回x除以p

......但也许有另一种方法.

笔记:

• 我用C++ 14ish术语表达了问题和我的方法,并且代码中的解决方案会很好,但是抽象解决方案(甚至是x86_64汇编中的解决方案)都可以.我确实想要一些适用于所有(无符号)整数类型的东西.
• 您可以忽略有符号整数类型.
• 我没有说明"快"是什么,但请注意硬件.

Answer 1

我想到的选项；

暴力破解：保持整数除以 10，直到得到零；它告诉你正在查看的数字的顺序（例如 860 需要 3 个班次 (86, 8, 0)，所以它是 10^3），然后返回 n/(10^order)

二分搜索：正如您所说，搜索 10 的幂，但它需要额外的变量和赋值，并且问题是，额外的跟踪信息是否会为您关心的数字类型带来回报？例如，如果大多数数字都很小，那么暴力破解可能会更快。

Bitshift 优化：计算需要执行多少次，x >> 1直到归零；这设置了您的搜索范围。例如，94需要7个轮班才能清除号码。因此它 < 128。因此，从 10^3 开始暴力搜索。您需要查找“bits=>order”。