如何在不将其转换为字符串且不知道长度的情况下获取给定 ***unsigned long long*** 的前 3 位数字
how can I get the first 3 digits of a given ***unsigned long long*** without converting it to string and without knowing is the length
如何获得给定 unsigned long long 的前 3 位数字
无需将其转换为字符串
现在数字的长度是固定的。
不使用除以 /10 的朴素方法。
像这样
int first_3_digits(unsigned long long number)
{
unsigned long long n = number;
while(n >= 1000){
n = n/10;
}
return n;
}
我接受了采访，他们说这个解决方案不够好
面试官说这个解决方案类似于二分查找。
我知道二进制搜索是如何工作的，但我不知道如何将它与这个问题联系起来。
找到“最佳”解决方案通常取决于您定义的重要标准。
如果你想要最小或最简单的解决方案，你的方法还不错。
如果你想要快速解决方案（并从面试官那里得到关于“二进制搜索”的提示），那么你可以尝试这样的事情（未测试）：
int first_3_digits(unsigned long long number)
{
unsigned long long n = number;
unsigned long long chopped;
// n has up to 20 digits. We need to chop up to 17 digits.
// Chop 8 digits
chopped = n / 100000000ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 12 digits,
// If we use old n we have up to 11 digits
// 9 more to go...
// Chop 4 digits
chopped = n / 10000ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 8 digits,
// If we use old n we have up to 7 digits
// 5 more to go...
// Chop 2 digits
chopped = n / 100ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 6 digits,
// If we use old n we have up to 5 digits
// 3 more to go...
// Chop 2 digits again
chopped = n / 100ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 4 digits,
// If we use old n we have up to 3 digits
// 1 more to go...
// Chop last digit if required.
if (n >= 1000)
{
n /= 10;
}
return n;
}
对于 64 位值，最大数量为 18446744073709551615，即 20 位。
我们必须删除最多 17 位数字。
由于这不是使用 2 的幂来截取位数的完美数字，我们重复该步骤以截取 2 位数字。
该解决方案可能会更快一些，但可能需要更多代码。
您可以使用十进制对数计算数字的长度（它的幂），然后使用十进制指数得到小于三个数量级的除数，然后用整数除以它：
#include <assert.h>
#include <math.h>
int first_3_digits(unsigned long long number)
{
if(number < 1000)
return number;
int number_length = int(floor(log10l(number)))+1;
assert(number_length > 3);
unsigned long long divider = exp10l(number_length - 3);
return number/divider;
}
int main()
{
assert(first_3_digits(0)==0);
assert(first_3_digits(999)==999);
assert(first_3_digits(1234)==123);
assert(first_3_digits(9876543210123456789ull)==987);
return 0;
}
这里是一个使用 log10 函数的简短解决方案：
int first_n_digits(unsigned long long number){
return number < 1000 ? number = (int)number : number = (int)(number/pow(10,(int)(log10(number)+1)-3));
}
现代处理器能够使用特定的 low-level 指令（例如 bsr 在主流 x86- 64 个处理器）。基于 this great previous post 可以非常快速地计算整数的 log10。这个想法是使用 查找 table 来进行 log2 和 log10 之间的转换。一旦计算出 log10，就可以使用另一个查找 table 来执行除以 10 ** log10(number)。但是，non-constant 64 位除法在几乎所有处理器上都非常昂贵。另一种解决方案是对所有可能的情况使用 switch，以便编译器可以为所有情况生成有效的代码，并使用快速 跳转 table。实际上，编译器可以通过比 non-constant 除法快得多的几条快速指令（即乘法和移位）来优化常量除法。虽然生成的代码不是很 beautiful/simple。这是：
#include <math.h>
#include <assert.h>
static inline unsigned int baseTwoDigits(unsigned long long x) {
return x ? 64 - __builtin_clzll(x) : 0;
}
static inline unsigned int baseTenDigits(unsigned long long x) {
static const unsigned char guess[65] = {
0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9,
10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19
};
static const unsigned long long tenToThe[] = {
1ull, 10ull, 100ull, 1000ull, 10000ull, 100000ull, 1000000ull, 10000000ull, 100000000ull,
1000000000ull, 10000000000ull, 100000000000ull, 1000000000000ull,
10000000000000ull, 100000000000000ull, 1000000000000000ull,
10000000000000000ull, 100000000000000000ull, 1000000000000000000ull,
10000000000000000000ull
};
unsigned int digits = guess[baseTwoDigits(x)];
return digits + (x >= tenToThe[digits]);
}
inline int optimized(unsigned long long number)
{
const unsigned int intLog = baseTenDigits(number);
switch(intLog)
{
case 0: return number;
case 1: return number;
case 2: return number;
case 3: return number;
case 4: return number / 10ull;
case 5: return number / 100ull;
case 6: return number / 1000ull;
case 7: return number / 10000ull;
case 8: return number / 100000ull;
case 9: return number / 1000000ull;
case 10: return number / 10000000ull;
case 11: return number / 100000000ull;
case 12: return number / 1000000000ull;
case 13: return number / 10000000000ull;
case 14: return number / 100000000000ull;
case 15: return number / 1000000000000ull;
case 16: return number / 10000000000000ull;
case 17: return number / 100000000000000ull;
case 18: return number / 1000000000000000ull;
case 19: return number / 10000000000000000ull;
case 20: return number / 100000000000000000ull;
default: assert(0); return 0;
}
}
请注意，此代码使用 non-standard 编译器 built-in __builtin_clzll 在 Clang 和 GCC 上均可用。对于 MSVC，请阅读 this post.
[Update] 之前的基准测试没有内联建议函数的代码，而不是其他函数，导致执行速度较慢（尤其是在 Clang 上）。使用 static+inline 帮助编译器正确地内联函数调用。
结果
这里是 QuickBench 上的方法分别在 GCC and Clang (with -O3). Note that the input distribution is chosen so that the logarithm are quite uniform and pseudo-random (ie. logarithm uniform) 上的结果。这个选择是因为面试官说 binary-search 是一个很好的解决方案，而这个分布是这种算法的最佳选择。
可以看出此解决方案是最快的。由于浮点舍入，Yakov Khodorkovski 和 qqNade 对大值给出了 错误结果 。为了清楚起见，qqNade 中的一个没有出现在基准测试中，因为它比原来的慢 10 倍以上。
Gerhardh 的解决方案使用 Clang 如此之快的原因是编译器能够部分生成快速的条件移动而不是慢速的条件分支。这种优化 非常聪明 因为这仅适用于 32 位整数（并且如果之前执行了关于常量除法的优化），但是 Clang 能够 知道 n 在 2 个第一个条件 之后已经足够小了！话虽这么说，这种优化是脆弱的，因为代码中的一些更改似乎经常会破坏它。
可以注意到 原始代码出奇地快（尤其是在 GCC 上）。这是由于 branch prediction。现代处理器执行许多迭代而不检查它们是否应该执行（并在需要时回滚）。每次迭代都非常快，因为优化了除以常量：在我的机器上它只需要 2 cycle/iterations。在现代 x86-64 Intel 处理器上，一个分支预测错误需要 14 个周期，而一个 well-predicted 分支只需要 1-2 个周期（类似于 AMD Zen 处理器）。平均迭代次数约为 9，只有最后一次迭代是昂贵的。 Gerhardh 的解决方案导致执行的指令少得多，但它可以导致 GCC 最多 4 个 miss-predicted 分支，Clang 最多 2 个。建议的解决方案仅产生 1 个间接 miss-predicted 分支（尽管处理器执行效率较低）。由于优化的实现在 Quickbench 上平均仅运行约 10 个周期，因此分支预测错误的影响是巨大的。
请注意，尽管总体趋势保持不变，但使用其他输入分布会对结果产生影响。以下是均匀分布的结果：GCC and Clang。原始算法明显较慢，因为平均位数是两倍（17~18 而不是 ~9），迭代次数也是如此。其他算法的速度与之前的分布相差不大，整体趋势保持不变。
结论
综上所述，Gerhardh 的解决方案相对table，简单且快速。新提出的解决方案更复杂，但它在 GCC 和 Clang 上都是最快的。因此，除非该功能的性能非常重要，否则应该优先使用Gerhardh的解决方案。
当面试官说：
the solution resembles a binary search
这证明面试官考虑到此功能的特定输入分布，并且该分布不是 unsigned long long 值范围内的均匀分布.在这一点上，有必要询问面试官他们期望什么样的输入分布，因为在不知道这一点的情况下不可能优化这样的算法。
特别是，如果输入是从 64 位无符号值范围的统一样本中选择的，那么以下简单函数将接近最优：
/* See Note 1 for this constant */
#define MAX_POWER (10ULL * 1000 * 1000 * 1000 * 1000 * 1000)
int first_3_digits(unsigned long long n) {
if (n >= 1000) { /* Almost always true but needed for correctness */
while (n < MAX_POWER * 100) n *= 10;
if (n >= MAX_POWER * 1000) n /= 10;
n /= MAX_POWER;
}
return n;
}
我希望这能证明预期的输入分布有多大的不同。上述解决方案针对输入接近最大位数的情况进行了优化，这几乎总是均匀分布的情况。在那种情况下，while 循环几乎不会执行（更准确地说，它会执行大约 1/1844 次）。
该解决方案还有一个优点，即 while 循环，即使执行，也只做 10 的乘法，而不是 10 的除法。GCC 和 Clang 都知道如何将常量除法优化为乘法和移位，但是a 乘法仍然更快，乘以 10 特别容易优化。 [注2]
备注
请注意，常量 MAX_POWER 是针对 unsigned long long 是 64 位值的情况预先计算的。虽然这很常见，但不能保证，而且它也是 unsigned long long 的最小可能大小。使用 C 预处理器计算正确的值是可能的，至少在一定程度上是这样，但它很乏味，所以我将其排除在外。需要的值是不大于ULLONG_MAX / 1000的10的最大次方。 （由于 unsigned long long 始终是 2 的幂，它不能是 10 的幂，如果更方便的话，测试同样可以用于小于 ULLONG_MAX / 1000 的最大 10 的幂。）
在benchmark provided by Jérôme Richard, whose sample inputs are chosen so that their logarithms are roughly uniform --a very different input distribution--, this comes out a bit slower than his optimised solution, although it's within the margin of error of the benchmark tool. (On the other hand, the code is quite a bit simpler.) On Jérôme's second benchmark, with a uniform sample, it comes out a lot faster.
二进制搜索的提示意味着最后几个测试和划分应该如下所示，使用 10 的幂：..., 8, 4, 2, 1
// Pseudo code
if (big enough)
divide by 100,000,000
if (big enough)
divide by 10,000
if (big enough)
divide by 100
if (big enough)
divide by 10
向后计算，对于 64 位 unsigned long long。
我们最多需要 5 个分区
由于 unsigned long long 可能比 64 宽，因此添加测试。
不仅提供解决方案，还提供测试工具来演示正确性。
示例：
#include <errno.h>
#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned first3(unsigned long long x) {
static const unsigned long long ten18 = 1000000ull * 1000000 * 1000000;
static const unsigned long long ten16 = 10000ull * 1000000 * 1000000;
static const unsigned long long ten10 = 10000ull * 1000000;
static const uint32_t ten8 = 100ul * 1000000;
static const uint32_t ten6 = 1000000u;
static const uint32_t ten4 = 10000u;
static const uint32_t ten3 = 1000u;
static const uint32_t ten2 = 100u;
// while loop used in case unsigned long long is more than 64-bit
// We could use macro-magic to make this an `if` for common 64-bit.
while (x >= ten18) {
x /= ten16;
}
if (x >= ten10) {
x /= ten8;
}
if (x >= ten6) {
x /= ten4;
}
uint32_t x32 = (uint32_t) x; // Let us switch to narrow math
if (x32 >= ten4) {
x32 /= ten2;
}
if (x32 >= ten3) {
x32 /= 10;
}
return (unsigned) x32;
}
测试代码
int test_first3(void) {
char buf[sizeof(unsigned long long) * CHAR_BIT];
for (size_t i = 1;; i++) {
for (int dig = '0'; dig <= '9'; dig += 9) {
memset(buf, dig, i);
if (dig == '0') {
buf[0]++;
}
buf[i] = '[=12=]';
errno = 0;
unsigned long long x = strtoull(buf, 0, 10);
if (errno) {
puts("Success!");
return 0;
}
unsigned f3 = first3(x);
char buf3[sizeof(unsigned) * CHAR_BIT];
int len = sprintf(buf3, "%u", f3);
printf("%2zu <%s> <%s>\n", i, buf3, buf);
if (len > 3) {
printf("i:%zu dig:%c\n", i, dig);
return -1;
}
if (strncmp(buf, buf3, 3) != 0) {
return -1;
}
}
}
}
int main(void) {
test_first3();
}
输出
1 <1> <1>
1 <9> <9>
2 <10> <10>
2 <99> <99>
3 <100> <100>
3 <999> <999>
4 <100> <1000>
4 <999> <9999>
5 <100> <10000>
5 <999> <99999>
...
17 <100> <10000000000000000>
17 <999> <99999999999999999>
18 <100> <100000000000000000>
18 <999> <999999999999999999>
19 <100> <1000000000000000000>
19 <999> <9999999999999999999>
20 <100> <10000000000000000000>
Success!
如何获得给定 unsigned long long 的前 3 位数字 无需将其转换为字符串 现在数字的长度是固定的。
不使用除以 /10 的朴素方法。
像这样
int first_3_digits(unsigned long long number)
{
unsigned long long n = number;
while(n >= 1000){
n = n/10;
}
return n;
}
我接受了采访，他们说这个解决方案不够好 面试官说这个解决方案类似于二分查找。 我知道二进制搜索是如何工作的，但我不知道如何将它与这个问题联系起来。
找到“最佳”解决方案通常取决于您定义的重要标准。 如果你想要最小或最简单的解决方案，你的方法还不错。
如果你想要快速解决方案（并从面试官那里得到关于“二进制搜索”的提示），那么你可以尝试这样的事情（未测试）：
int first_3_digits(unsigned long long number)
{
unsigned long long n = number;
unsigned long long chopped;
// n has up to 20 digits. We need to chop up to 17 digits.
// Chop 8 digits
chopped = n / 100000000ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 12 digits,
// If we use old n we have up to 11 digits
// 9 more to go...
// Chop 4 digits
chopped = n / 10000ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 8 digits,
// If we use old n we have up to 7 digits
// 5 more to go...
// Chop 2 digits
chopped = n / 100ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 6 digits,
// If we use old n we have up to 5 digits
// 3 more to go...
// Chop 2 digits again
chopped = n / 100ull;
if (chopped >= 100)
{
n = chopped;
}
// chopped has up to 4 digits,
// If we use old n we have up to 3 digits
// 1 more to go...
// Chop last digit if required.
if (n >= 1000)
{
n /= 10;
}
return n;
}
对于 64 位值，最大数量为 18446744073709551615，即 20 位。
我们必须删除最多 17 位数字。
由于这不是使用 2 的幂来截取位数的完美数字，我们重复该步骤以截取 2 位数字。
该解决方案可能会更快一些，但可能需要更多代码。
您可以使用十进制对数计算数字的长度（它的幂），然后使用十进制指数得到小于三个数量级的除数，然后用整数除以它：
#include <assert.h>
#include <math.h>
int first_3_digits(unsigned long long number)
{
if(number < 1000)
return number;
int number_length = int(floor(log10l(number)))+1;
assert(number_length > 3);
unsigned long long divider = exp10l(number_length - 3);
return number/divider;
}
int main()
{
assert(first_3_digits(0)==0);
assert(first_3_digits(999)==999);
assert(first_3_digits(1234)==123);
assert(first_3_digits(9876543210123456789ull)==987);
return 0;
}
这里是一个使用 log10 函数的简短解决方案：
int first_n_digits(unsigned long long number){
return number < 1000 ? number = (int)number : number = (int)(number/pow(10,(int)(log10(number)+1)-3));
}
现代处理器能够使用特定的 low-level 指令（例如 bsr 在主流 x86- 64 个处理器）。基于 this great previous post 可以非常快速地计算整数的 log10。这个想法是使用 查找 table 来进行 log2 和 log10 之间的转换。一旦计算出 log10，就可以使用另一个查找 table 来执行除以 10 ** log10(number)。但是，non-constant 64 位除法在几乎所有处理器上都非常昂贵。另一种解决方案是对所有可能的情况使用 switch，以便编译器可以为所有情况生成有效的代码，并使用快速 跳转 table。实际上，编译器可以通过比 non-constant 除法快得多的几条快速指令（即乘法和移位）来优化常量除法。虽然生成的代码不是很 beautiful/simple。这是：
#include <math.h>
#include <assert.h>
static inline unsigned int baseTwoDigits(unsigned long long x) {
return x ? 64 - __builtin_clzll(x) : 0;
}
static inline unsigned int baseTenDigits(unsigned long long x) {
static const unsigned char guess[65] = {
0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4,
5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9, 9,
10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 14, 14, 14, 15,
15, 15, 15, 16, 16, 16, 17, 17, 17, 18, 18, 18, 18, 19
};
static const unsigned long long tenToThe[] = {
1ull, 10ull, 100ull, 1000ull, 10000ull, 100000ull, 1000000ull, 10000000ull, 100000000ull,
1000000000ull, 10000000000ull, 100000000000ull, 1000000000000ull,
10000000000000ull, 100000000000000ull, 1000000000000000ull,
10000000000000000ull, 100000000000000000ull, 1000000000000000000ull,
10000000000000000000ull
};
unsigned int digits = guess[baseTwoDigits(x)];
return digits + (x >= tenToThe[digits]);
}
inline int optimized(unsigned long long number)
{
const unsigned int intLog = baseTenDigits(number);
switch(intLog)
{
case 0: return number;
case 1: return number;
case 2: return number;
case 3: return number;
case 4: return number / 10ull;
case 5: return number / 100ull;
case 6: return number / 1000ull;
case 7: return number / 10000ull;
case 8: return number / 100000ull;
case 9: return number / 1000000ull;
case 10: return number / 10000000ull;
case 11: return number / 100000000ull;
case 12: return number / 1000000000ull;
case 13: return number / 10000000000ull;
case 14: return number / 100000000000ull;
case 15: return number / 1000000000000ull;
case 16: return number / 10000000000000ull;
case 17: return number / 100000000000000ull;
case 18: return number / 1000000000000000ull;
case 19: return number / 10000000000000000ull;
case 20: return number / 100000000000000000ull;
default: assert(0); return 0;
}
}
请注意，此代码使用 non-standard 编译器 built-in __builtin_clzll 在 Clang 和 GCC 上均可用。对于 MSVC，请阅读 this post.
[Update] 之前的基准测试没有内联建议函数的代码，而不是其他函数，导致执行速度较慢（尤其是在 Clang 上）。使用 static+inline 帮助编译器正确地内联函数调用。
结果
这里是 QuickBench 上的方法分别在 GCC and Clang (with -O3). Note that the input distribution is chosen so that the logarithm are quite uniform and pseudo-random (ie. logarithm uniform) 上的结果。这个选择是因为面试官说 binary-search 是一个很好的解决方案，而这个分布是这种算法的最佳选择。
可以看出此解决方案是最快的。由于浮点舍入，Yakov Khodorkovski 和 qqNade 对大值给出了 错误结果 。为了清楚起见，qqNade 中的一个没有出现在基准测试中，因为它比原来的慢 10 倍以上。
Gerhardh 的解决方案使用 Clang 如此之快的原因是编译器能够部分生成快速的条件移动而不是慢速的条件分支。这种优化 非常聪明 因为这仅适用于 32 位整数（并且如果之前执行了关于常量除法的优化），但是 Clang 能够 知道 n 在 2 个第一个条件 之后已经足够小了！话虽这么说，这种优化是脆弱的，因为代码中的一些更改似乎经常会破坏它。
可以注意到 原始代码出奇地快（尤其是在 GCC 上）。这是由于 branch prediction。现代处理器执行许多迭代而不检查它们是否应该执行（并在需要时回滚）。每次迭代都非常快，因为优化了除以常量：在我的机器上它只需要 2 cycle/iterations。在现代 x86-64 Intel 处理器上，一个分支预测错误需要 14 个周期，而一个 well-predicted 分支只需要 1-2 个周期（类似于 AMD Zen 处理器）。平均迭代次数约为 9，只有最后一次迭代是昂贵的。 Gerhardh 的解决方案导致执行的指令少得多，但它可以导致 GCC 最多 4 个 miss-predicted 分支，Clang 最多 2 个。建议的解决方案仅产生 1 个间接 miss-predicted 分支（尽管处理器执行效率较低）。由于优化的实现在 Quickbench 上平均仅运行约 10 个周期，因此分支预测错误的影响是巨大的。
请注意，尽管总体趋势保持不变，但使用其他输入分布会对结果产生影响。以下是均匀分布的结果：GCC and Clang。原始算法明显较慢，因为平均位数是两倍（17~18 而不是 ~9），迭代次数也是如此。其他算法的速度与之前的分布相差不大，整体趋势保持不变。
结论
综上所述，Gerhardh 的解决方案相对table，简单且快速。新提出的解决方案更复杂，但它在 GCC 和 Clang 上都是最快的。因此，除非该功能的性能非常重要，否则应该优先使用Gerhardh的解决方案。
当面试官说：
the solution resembles a binary search
这证明面试官考虑到此功能的特定输入分布，并且该分布不是 unsigned long long 值范围内的均匀分布.在这一点上，有必要询问面试官他们期望什么样的输入分布，因为在不知道这一点的情况下不可能优化这样的算法。
特别是，如果输入是从 64 位无符号值范围的统一样本中选择的，那么以下简单函数将接近最优：
/* See Note 1 for this constant */
#define MAX_POWER (10ULL * 1000 * 1000 * 1000 * 1000 * 1000)
int first_3_digits(unsigned long long n) {
if (n >= 1000) { /* Almost always true but needed for correctness */
while (n < MAX_POWER * 100) n *= 10;
if (n >= MAX_POWER * 1000) n /= 10;
n /= MAX_POWER;
}
return n;
}
我希望这能证明预期的输入分布有多大的不同。上述解决方案针对输入接近最大位数的情况进行了优化，这几乎总是均匀分布的情况。在那种情况下，while 循环几乎不会执行（更准确地说，它会执行大约 1/1844 次）。
该解决方案还有一个优点，即 while 循环，即使执行，也只做 10 的乘法，而不是 10 的除法。GCC 和 Clang 都知道如何将常量除法优化为乘法和移位，但是a 乘法仍然更快，乘以 10 特别容易优化。 [注2]
备注
请注意，常量
MAX_POWER是针对unsigned long long是 64 位值的情况预先计算的。虽然这很常见，但不能保证，而且它也是unsigned long long的最小可能大小。使用 C 预处理器计算正确的值是可能的，至少在一定程度上是这样，但它很乏味，所以我将其排除在外。需要的值是不大于ULLONG_MAX / 1000的10的最大次方。 （由于unsigned long long始终是 2 的幂，它不能是 10 的幂，如果更方便的话，测试同样可以用于小于ULLONG_MAX / 1000的最大 10 的幂。）在benchmark provided by Jérôme Richard, whose sample inputs are chosen so that their logarithms are roughly uniform --a very different input distribution--, this comes out a bit slower than his optimised solution, although it's within the margin of error of the benchmark tool. (On the other hand, the code is quite a bit simpler.) On Jérôme's second benchmark, with a uniform sample, it comes out a lot faster.
二进制搜索的提示意味着最后几个测试和划分应该如下所示，使用 10 的幂：..., 8, 4, 2, 1
// Pseudo code if (big enough) divide by 100,000,000 if (big enough) divide by 10,000 if (big enough) divide by 100 if (big enough) divide by 10向后计算，对于 64 位
我们最多需要 5 个分区unsigned long long。由于
unsigned long long可能比 64 宽，因此添加测试。不仅提供解决方案，还提供测试工具来演示正确性。
示例：
#include <errno.h>
#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned first3(unsigned long long x) {
static const unsigned long long ten18 = 1000000ull * 1000000 * 1000000;
static const unsigned long long ten16 = 10000ull * 1000000 * 1000000;
static const unsigned long long ten10 = 10000ull * 1000000;
static const uint32_t ten8 = 100ul * 1000000;
static const uint32_t ten6 = 1000000u;
static const uint32_t ten4 = 10000u;
static const uint32_t ten3 = 1000u;
static const uint32_t ten2 = 100u;
// while loop used in case unsigned long long is more than 64-bit
// We could use macro-magic to make this an `if` for common 64-bit.
while (x >= ten18) {
x /= ten16;
}
if (x >= ten10) {
x /= ten8;
}
if (x >= ten6) {
x /= ten4;
}
uint32_t x32 = (uint32_t) x; // Let us switch to narrow math
if (x32 >= ten4) {
x32 /= ten2;
}
if (x32 >= ten3) {
x32 /= 10;
}
return (unsigned) x32;
}
测试代码
int test_first3(void) {
char buf[sizeof(unsigned long long) * CHAR_BIT];
for (size_t i = 1;; i++) {
for (int dig = '0'; dig <= '9'; dig += 9) {
memset(buf, dig, i);
if (dig == '0') {
buf[0]++;
}
buf[i] = '[=12=]';
errno = 0;
unsigned long long x = strtoull(buf, 0, 10);
if (errno) {
puts("Success!");
return 0;
}
unsigned f3 = first3(x);
char buf3[sizeof(unsigned) * CHAR_BIT];
int len = sprintf(buf3, "%u", f3);
printf("%2zu <%s> <%s>\n", i, buf3, buf);
if (len > 3) {
printf("i:%zu dig:%c\n", i, dig);
return -1;
}
if (strncmp(buf, buf3, 3) != 0) {
return -1;
}
}
}
}
int main(void) {
test_first3();
}
输出
1 <1> <1>
1 <9> <9>
2 <10> <10>
2 <99> <99>
3 <100> <100>
3 <999> <999>
4 <100> <1000>
4 <999> <9999>
5 <100> <10000>
5 <999> <99999>
...
17 <100> <10000000000000000>
17 <999> <99999999999999999>
18 <100> <100000000000000000>
18 <999> <999999999999999999>
19 <100> <1000000000000000000>
19 <999> <9999999999999999999>
20 <100> <10000000000000000000>
Success!