如何最快地获取一个整数的最高位数字？

Question

如何最快地实现

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

（返回例如356431的3，71的7和9的9）？

我能想到的最好方法是：

• constexpr-计算适合T的“中等大小”10次幂。
• 执行二进制搜索（在10次幂上，可能使用constexpr构造的查找表），以找到p，低于x的最高10次幂。
• 返回x除以p

...但也许还有其他方法。

注意：

• 我用C++14ish术语表达了问题和我的方法，代码解决方案很好，但抽象解决方案（甚至是x86_64汇编中的解决方案）都可以。不过，我希望能够适用于所有（无符号）整数类型。
• 您可以忽略有符号整数类型。
• 我没有指定“快速”的含义，但请考虑硬件因素。

- einpoklum

---

使用字符串不允许吗？ - yobro97

@manlio 确实，甚至最佳答案也和我的匹配 :P - Vesper

@yobro97：任何涉及字符串的工作都不可能有快速解决方案。 - einpoklum

Answer 1

最佳选择似乎是将CLZ方法与预计算的10的幂相结合。所以，在伪代码中：

powers10=[1,1,1,1,10,10,10,10,100,100...]; // contains powers of 10 map to CLZ values
int firstDigit(unsigned INT_TYPE a) {
    if (a<10) return a; // one digit, screw it
    int j=typesize(a)-clz(a);
    if (j==3) return 1; // 10-16 hit this, return 1
    int k=a/powers10[j];
    if (k>9) return 1; else return k;
}

typesize()函数返回long long类型的大小为64，int类型的大小为32，short int类型的大小为16。

- Vesper

---

这应该会非常慢，因为它需要从 RAM 中读取。如果您重复运行它，它会稍微好一些（希望是 L1 缓存），但我仍然非常怀疑这是否是最快的方法。 - einpoklum

@einpoklum 哦，就硬件而言，将整个表格放入L1缓存比进行所需的十次幂计算更便宜，而且除法始终比乘法更昂贵，尤其是通过常数相乘。因此，重复除以10的成本比仅进行一次内存访问的除法更高。而且，“powers10”可以位于堆栈上，因为它非常小，只有64x8=512字节，而且堆栈很可能位于具有L1缓存的任何系统上。 - Vesper

有一些替代方案可以避免重复除以10，而且不需要从RAM中读取任何内容 - 例如使用仅仅是乘法的10次幂，这是非常便宜的。至于L1缓存 - 你可能能够在那里保留你的表格，也可能不能。 - einpoklum

如果你总是调用函数，那么堆栈是否总在L1上？此外，您真的需要批处理这么多数字才能使L1问题相关吗？ - Vesper

如果您需要每次调用函数，那么这本身就是一个问题。如果您在另一个函数中工作，并且需要重复计算最高十进制数字的某些数据结构，则可能会反复从L1缓存中驱逐数组。不过，我猜您大多数情况下都会在L1缓存中找到它。 - einpoklum

Answer 2

新的x86芯片支持lzcnt指令，该指令可以告诉你一个整数开头的清除位数。您可以使用内置编译器函数来访问它，例如以下函数（来自GCC）：

 unsigned short __builtin_ia32_lzcnt_16(unsigned short);
 unsigned int __builtin_ia32_lzcnt_u32(unsigned int);
 unsigned long long __builtin_ia32_lzcnt_u64 (unsigned long long);

您可以将此与一个查找表相结合，该表包含640个值，指示以0-9中每个数字开头的具有相应数量的清除位的整数的下限和上限。实际上，您可以通过将lzcnt值向右移动3个位置来节省空间；与第一个小数位的对应关系仍将是唯一的。

- r3mainer

Answer 3

使用lzcnt指令，可以为每个前导零位的数字构建除数表。例如，对于无符号64位数字：

lz | range   | div
---+---------+----
64 |   0     |   1
63 |   1     |   1
62 |   2-3   |   1
61 |   4-7   |   1
60 |   8-15  |   1
59 |  16-31  |  10
58 |  32-63  |  10
57 |  64-127 |  10
56 | 128-255 | 100
...
 0 | 9223372036854775808-18446744073709551615 | 1000000000000000000

然后计算变成了：

leading_zero_bits = lzcnt(x);
leading_digit = x / divisor_table[leading_zero_bits];
if (leading_digit >= 10) leading_digit = 1;

除法的结果始终小于20，因此只需要对10到19之间的商进行简单检查。常数除法也可以进行优化。

- nwellnhof

---

你需要确保该表位于你的 L1 缓存中，才能使其运行速度快。 - einpoklum

Answer 4

我想到的选项有：

暴力破解：不断地将数字除以10，直到得到0；这告诉你你正在查找哪个数字（例如860需要3次操作（86、8、0），所以它是10^3），然后返回n/(10^order)

二分查找：就像你说的，搜索10的幂，但它需要额外的变量和赋值，问题在于，这种额外的跟踪信息是否对你关心的数字产生了足够的效益？例如，如果大多数数字都很小，那么暴力破解可能会更快。

位移优化：计算需要多少次x >> 1才能得到0；这设置了您搜索的范围。例如，94需要7次移位才能清除该数字。因此它小于128。因此，在10^3处开始暴力搜索。您需要一个查找表来查找位=>顺序。

- Steve Cooper

---

除法有点昂贵...我认为至少对于32位和64位数字，值得做一些比这更聪明的事情。至于“计算移位”-没有必要，现在我们在硬件上有CLZ。 - einpoklum

我并没有足够的汇编智慧来提供帮助，除了提供一些你可能能够挽救的垃圾。 - Steve Cooper

话虽如此，如果您能够执行 clz，那么将该数字转换为十的最大幂次，您只需要尝试少量的测试即可。我不知道足够多的知识来提供更多帮助。 - Steve Cooper

是的，clz 似乎是最好的方法，然后你就有一个准备好的10的幂可以除以，至少一半的时间，比如如果32位数字的 clz 返回27，则该数字在16-32区域内，因此除以10即可得到答案。如果 clz 是25，则该区域为64-127，因此再次除以10并进行比较，如果结果大于9，则直接返回1。对于更高的10的幂，也是同样的方法，但首先要将它们存储起来。 - Vesper