3 年大厂工作经验面试竟然要我手写 atoi 函数
前言
手写代码是面试过程常见的环节之一，但是一般都是手写算法题，此次面试官要我手写一个基本的 C 语言 atoi，内心一惊，这怎么感觉像是校招…
先说一下 atoi 函数的功能，它是一个 C 标准库函数，将给定的 C 风格字符串转换为 int。
本题虽然简单，但是如果之前没有练习书手写 atoi，要想写出一个让面试官满意的接近标准库水准的 atoi 并非易事，因为有不少实现细节需要考虑。
我遇到的问题
由于第一次手写 atoi，有点猝不及防，内心还是有点慌乱的，因为自己对 atoi 地认知也仅仅停留在知其作用的程度，对其实现细节并没有深度研究过。就这样，我在思考如何书写 atoi 前遇到了不少细节问题。
（1）如果传入的参数非法，比如并非是一个数字型字符串，函数该返回多少来表示参数异常呢？返回 -1 吗？但是如果待转换的字符串是 “-1”，那岂不是冲突了？
（2）如果待转换的是负数，如果将最后的正数转换为负数呢？
（3）考虑的不够全面，以为 atoi 对入参要完全符合条件。事实上 atoi 比我想象中的容错性更高。在找到第一个非空白字符之前，该函数首先根据需要丢弃尽可能多的空白字符（如 space 和 tab)。然后，从这个字符开始，取一个可选的正负号，后面跟着尽可能多的基数为 10 的数字，并将它们解释为一个数值。字符串可以在构成整数的字符之后包含其他字符，这些字符被忽略，对此函数的行为没有任何影响；
（4）如果优雅地将数字字符转换为对应的数值，比如将字符 ‘0’ 转为数值 0；
（5）如果转换的数值溢出了该返回什么呢？
如果没有意识到上面的问题，或者想到了但是没法解决，那么真的很难写出一个让面试满意地 atoi。
标准库的实现
下面看一下标准库 atoi 地做法吧。
第一个问题，atoi 做法是入参字符串为空或仅包含空白字符，则不执行转换并返回零；
第二个问题，我想复杂了，实际上正数前加个减号即可变为负数；
第三个问题，实现一个函数时，要考虑到入参的各种情况并尽可能地提供高容错性的实现，就像 atoi 会跳过前面的空白字符以及丢弃尾部非数字字符。
第四个问题，最容易想到的是通过 switch case 枚举出十个字符并返回对应的数字。这个很容易实现，但是不够优雅。标准库的做法是：
#ifdef USE_WIDE_CHAR
# define L_(Ch) L##Ch
#else
# define L_(Ch) Ch
#endif
if (c >= L_('0') && c <= L_('9'))
c -= L_('0');这个做法非常简洁精妙，对数字字符直接与字符 ‘0’ 相减即可得到其对应的数值。
第五个问题，标准库的做法是返回 int 所能表示的最大正数和最小负数。int 能表示的最小负数为 -0x8000 0000（-2,147,483,648），最大正数为 0x7fff ffff（2,147,483,647）。
这里有需要知道 atoi 是调用函数 strtol，strtol 再调用函数 __strtol_l 来完成转换。因为 strtol 返回类型是 long int，而 long int 在 32 位的程序和 64 位的程序中位宽度是不同的，所以底层实现时需要根据程序的位宽来返回不同的最大最小值。相关的宏定义如下：
#ifdef QUAD
# define STRTOL_LONG_MIN LONG_LONG_MIN
# define STRTOL_LONG_MAX LONG_LONG_MAX
#else
# define STRTOL_LONG_MIN LONG_MIN
# define STRTOL_LONG_MAX LONG_MAX
#endif其中 LONG_LONG_MIN 和 LONG_LONG_MAX 我在标准库源码中并未找到其定义，原来其定义只存在于 GCC 版本低于 3.0，已被 LLONG_MIN 与 LLONG_MAX 取代。LLONG_MIN 与 LLONG_MAX 在 inclue/limits.h 头文件中的定义如下：
# define LLONG_MAX 9223372036854775807LL
# define LLONG_MIN (-LLONG_MAX - 1LL)另外 LONG_MIN 和 LONG_MAX 定义在文件 inclue/limits.h 头文件中。
# if __WORDSIZE == 64
# define LONG_MAX 9223372036854775807L
# else
# define LONG_MAX 2147483647L
# endif
# define LONG_MIN (-LONG_MAX - 1L)从这里可以看出，标准库是根据宏变量 __WORDSIZE 来判断程序是 32 位还是 64 位，宏 __WORDSIZE 可以通过 gcc 命令的编译选项 -m32 或者 -m64 来控制。
如果是自己实现的话，可以根据指针变量的位宽来判断程序是 32bits 还是 64bits：
#define IS64BIT ((sizeof(NULL)==8))如果面试时能在短时间内考虑到上面的问题并想到对应的解决办法，那么写出让面试官满意的代码也八九不离十了，最后就是展现码代码的基本功了。
大家先欣赏一下 GNU C 的实现吧，以 glic-2.31 为例。
下载好源码包后对其解压，在目录 stdlib 下 atoi.c 中找到 atoi 的定义。
//
// atoi.c
//
/* Convert a string to an int. */
int
atoi (const char *nptr)
{
return (int) strtol (nptr, (char **) NULL, 10);
}
libc_hidden_def (atoi)可见 atoi 是调用了 strtol 函数，继续寻找 strtol 的定义，最终在 strtol.c 中找到了其定义。
//
// strtol.c
//
INT
__strtol (const STRING_TYPE *nptr, STRING_TYPE **endptr, int base)
{
return INTERNAL (__strtol_l) (nptr, endptr, base, 0, _NL_CURRENT_LOCALE);
}
weak_alias (__strtol, strtol)
libc_hidden_weak (strtol)weak_alias (__strtol, strtol) 表明 strtol 的别称是 __strtol。这里可以看出，__strtol 也并非直接实现转换功能，而是调用 __strtol_l 函数实现转换。下面继续寻找 __strtol_l 函数的定义，其定义在 strtol_l.c 文件中。
//
// strtol_l.c
//
/* Convert NPTR to an `unsigned long int' or `long int' in base BASE.
If BASE is 0 the base is determined by the presence of a leading
zero, indicating octal or a leading "0x" or "0X", indicating hexadecimal.
If BASE is < 2 or > 36, it is reset to 10.
If ENDPTR is not NULL, a pointer to the character after the last
one converted is stored in *ENDPTR. */
INT
INTERNAL (__strtol_l) (const STRING_TYPE *nptr, STRING_TYPE **endptr,
int base, int group, locale_t loc)
{
int negative;
unsigned LONG int cutoff;
unsigned int cutlim;
unsigned LONG int i;
const STRING_TYPE *s;
UCHAR_TYPE c;
const STRING_TYPE *save, *end;
int overflow;
#ifndef USE_WIDE_CHAR
size_t cnt;
#endif
#ifdef USE_NUMBER_GROUPING
struct __locale_data *current = loc->__locales[LC_NUMERIC];
/* The thousands character of the current locale. */
# ifdef USE_WIDE_CHAR
wchar_t thousands = L'\0';
# else
const char *thousands = NULL;
size_t thousands_len = 0;
# endif
/* The numeric grouping specification of the current locale,
in the format described in <locale.h>. */
const char *grouping;
if (__glibc_unlikely (group))
{
grouping = _NL_CURRENT (LC_NUMERIC, GROUPING);
if (*grouping <= 0 || *grouping == CHAR_MAX)
grouping = NULL;
else
{
/* Figure out the thousands separator character. */
# ifdef USE_WIDE_CHAR
# ifdef _LIBC
thousands = _NL_CURRENT_WORD (LC_NUMERIC,
_NL_NUMERIC_THOUSANDS_SEP_WC);
# endif
if (thousands == L'\0')
grouping = NULL;
# else
# ifdef _LIBC
thousands = _NL_CURRENT (LC_NUMERIC, THOUSANDS_SEP);
# endif
if (*thousands == '\0')
{
thousands = NULL;
grouping = NULL;
}
# endif
}
}
else
grouping = NULL;
#endif
if (base < 0 || base == 1 || base > 36)
{
__set_errno (EINVAL);
return 0;
}
save = s = nptr;
/* Skip white space. */
while (ISSPACE (*s))
++s;
if (__glibc_unlikely (*s == L_('\0')))
goto noconv;
/* Check for a sign. */
negative = 0;
if (*s == L_('-'))
{
negative = 1;
++s;
}
else if (*s == L_('+'))
++s;
/* Recognize number prefix and if BASE is zero, figure it out ourselves. */
if (*s == L_('0'))
{
if ((base == 0 || base == 16) && TOUPPER (s[1]) == L_('X'))
{
s += 2;
base = 16;
}
else if (base == 0)
base = 8;
}
else if (base == 0)
base = 10;
/* Save the pointer so we can check later if anything happened. */
save = s;
#ifdef USE_NUMBER_GROUPING
if (base != 10)
grouping = NULL;
if (__glibc_unlikely (grouping != NULL))
{
# ifndef USE_WIDE_CHAR
thousands_len = strlen (thousands);
# endif
/* Find the end of the digit string and check its grouping. */
end = s;
if (
# ifdef USE_WIDE_CHAR
*s != thousands
# else
({ for (cnt = 0; cnt < thousands_len; ++cnt)
if (thousands[cnt] != end[cnt])
break;
cnt < thousands_len; })
# endif
)
{
for (c = *end; c != L_('\0'); c = *++end)
if (((STRING_TYPE) c < L_('0') || (STRING_TYPE) c > L_('9'))
# ifdef USE_WIDE_CHAR
&& (wchar_t) c != thousands
# else
&& ({ for (cnt = 0; cnt < thousands_len; ++cnt)
if (thousands[cnt] != end[cnt])
break;
cnt < thousands_len; })
# endif
&& (!ISALPHA (c)
|| (int) (TOUPPER (c) - L_('A') + 10) >= base))
break;
# ifdef USE_WIDE_CHAR
end = __correctly_grouped_prefixwc (s, end, thousands, grouping);
# else
end = __correctly_grouped_prefixmb (s, end, thousands, grouping);
# endif
}
}
else
#endif
end = NULL;
/* Avoid runtime division; lookup cutoff and limit. */
cutoff = cutoff_tab[base - 2];
cutlim = cutlim_tab[base - 2];
overflow = 0;
i = 0;
c = *s;
if (sizeof (long int) != sizeof (LONG int))
{
unsigned long int j = 0;
unsigned long int jmax = jmax_tab[base - 2];
for (;c != L_('\0'); c = *++s)
{
if (s == end)
break;
if (c >= L_('0') && c <= L_('9'))
c -= L_('0');
#ifdef USE_NUMBER_GROUPING
# ifdef USE_WIDE_CHAR
else if (grouping && (wchar_t) c == thousands)
continue;
# else
else if (thousands_len)
{
for (cnt = 0; cnt < thousands_len; ++cnt)
if (thousands[cnt] != s[cnt])
break;
if (cnt == thousands_len)
{
s += thousands_len - 1;
continue;
}
if (ISALPHA (c))
c = TOUPPER (c) - L_('A') + 10;
else
break;
}
# endif
#endif
else if (ISALPHA (c))
c = TOUPPER (c) - L_('A') + 10;
else
break;
if ((int) c >= base)
break;
/* Note that we never can have an overflow. */
else if (j >= jmax)
{
/* We have an overflow. Now use the long representation. */
i = (unsigned LONG int) j;
goto use_long;
}
else
j = j * (unsigned long int) base + c;
}
i = (unsigned LONG int) j;
}
else
for (;c != L_('\0'); c = *++s)
{
if (s == end)
break;
if (c >= L_('0') && c <= L_('9'))
c -= L_('0');
#ifdef USE_NUMBER_GROUPING
# ifdef USE_WIDE_CHAR
else if (grouping && (wchar_t) c == thousands)
continue;
# else
else if (thousands_len)
{
for (cnt = 0; cnt < thousands_len; ++cnt)
if (thousands[cnt] != s[cnt])
break;
if (cnt == thousands_len)
{
s += thousands_len - 1;
continue;
}
if (ISALPHA (c))
c = TOUPPER (c) - L_('A') + 10;
else
break;
}
# endif
#endif
else if (ISALPHA (c))
c = TOUPPER (c) - L_('A') + 10;
else
break;
if ((int) c >= base)
break;
/* Check for overflow. */
if (i > cutoff || (i == cutoff && c > cutlim))
overflow = 1;
else
{
use_long:
i *= (unsigned LONG int) base;
i += c;
}
}
/* Check if anything actually happened. */
if (s == save)
goto noconv;
/* Store in ENDPTR the address of one character
past the last character we converted. */
if (endptr != NULL)
*endptr = (STRING_TYPE *) s;
#if !UNSIGNED
/* Check for a value that is within the range of
`unsigned LONG int', but outside the range of `LONG int'. */
if (overflow == 0
&& i > (negative
? -((unsigned LONG int) (STRTOL_LONG_MIN + 1)) + 1
: (unsigned LONG int) STRTOL_LONG_MAX))
overflow = 1;
#endif
if (__glibc_unlikely (overflow))
{
__set_errno (ERANGE);
#if UNSIGNED
return STRTOL_ULONG_MAX;
#else
return negative ? STRTOL_LONG_MIN : STRTOL_LONG_MAX;
#endif
}
/* Return the result of the appropriate sign. */
return negative ? -i : i;
noconv:
/* We must handle a special case here: the base is 0 or 16 and the
first two characters are '0' and 'x', but the rest are no
hexadecimal digits. This is no error case. We return 0 and
ENDPTR points to the `x`. */
if (endptr != NULL)
{
if (save - nptr >= 2 && TOUPPER (save[-1]) == L_('X')
&& save[-2] == L_('0'))
*endptr = (STRING_TYPE *) &save[-1];
else
/* There was no number to convert. */
*endptr = (STRING_TYPE *) nptr;
}
return 0L;
}damm it！这简直是老太婆的裹脚布，又臭又长，难怪我写不出让面试官满意的 atoi，原来上面才是面试官想要的答案。还是冷静下来，细细品味标准库的魅力。
第一部分是定义了函数中用到的局部变量。
第二部分是对字符串分组的处理，比如对于很长的数字，一般会使用逗号按照 3 个数字进行分组，例如 123,456,789。
第三部分是对数值基数的判断，如果非法，设置全局环境变量 errno 为 EINVAL（参数非法）并返回 0。
第四部分跳过空白字符。
第五部分检查数值符号，判断是否是负数。
第六部分检查数值前缀，0 表示八进制，0x 或 0X 表示 16 进制，否则为 10 进制。
第七部分开始执行转换逻辑。
以上大致是函数 __strtol_l 的内容，__strtol_l 事无巨细，面面俱到，完成数值型字符串到数值的转换，包括对八进制和十六进制数值的转换。atoi 实现的是十进制数值的转换，只是 __strtol_l 功能的一部分。
适合面试手写的 atoi 实现
如果只是应对面试，书写上面的代码不合适，因为使用了大量的宏变量且包括了宽字符与数值分组的特殊处理，短时间内写出面面俱到的函数是不现实的，下面结合我们上面考虑到的几个问题点，给出适合手写的简易版本。
#include <stdio.h>
#include <ctype.h>
#include <limits.h>
// @brief: atoi converts a decimal value string to the corresponding value
int myatoi(const char* s){
// check null pointer
if (s == NULL) return 0;
int i,sign;
unsigned int n;
// skip white space
for (i = 0; isspace(s[i]); i++);
// get sign and skip
sign = (s[i]=='-')?-1:1;
if(s[i]=='+' || s[i]=='-') i++;
// convert numeric characters to numeric value
for(n=0; isdigit(s[i]); i++){
n = 10 * n + (s[i] - '0');
}
// overflow judgment
if (sign == 1 && n > INT_MAX) return INT_MAX;
if (sign == -1 && n > INT_MAX) return INT_MIN;
return sign * n;
}其中函数 isspace() 与 isdigit() 是 C 标准库函数，申明于头文件 ctype.h。宏 INT_MAX 与 INT_MIN 定义在头文件 limits.h，定义如下：
# define INT_MIN (-INT_MAX - 1)
# define INT_MAX 2147483647功能验证：
int main() {
// normal positive int value with white-space character in front
const char* s0 = "\t1";
printf("1=%d\n", myatoi(s0));
// normal negtive int value with white-space character in front
const char* s1 = "\t-1";
printf("-1=%d\n", myatoi(s1));
// null pointer
const char* s3 = NULL;
printf("NULL=%d\n", myatoi(s3));
// invalid decimal value string
const char* s4 = "a123b";
printf("a123b=%d\n", myatoi(s4));
// out of max range
const char* s5 = "2147483648";
printf("2147483648=%d\n", myatoi(s5));
// out of min range
const char* s6 = "-2147483649";
printf("-2147483649=%d\n", myatoi(s6));
}运行输出：
1=1
-1=-1
NULL=0
a123b=0
2147483648=2147483647
-2147483649=-2147483648看似简单的函数正真写起来并不容易，对每一道面试题保持敬畏之心。
参考文献
[1] cplusplus.atoi [2] Index of /gnu/glibc [3] Range of Type (The GNU C Library) [4] 博客园.C语言itoa()函数和atoi()函数详解(整数转字符C实现)