面试题67：把字符串转换成整数

以严格的全串十进制解析为例，完整走过需求澄清、符号处理、逐位累加、32位溢出判断、状态表达与边界测试。

学习目标

  • 能解释"返回值+状态"接口如何区分合法 0 与转换失败
  • 能实现全串十进制解析（符号、逐位累加、32 位溢出判断）
  • 能说明负数沿负方向累加与上下界不对称的原因

从“结果是0”为什么仍没有答案开始

题目要求编写StrToInt，把字符串转换成整数，且不能使用或类似库函数。真正困难的不是把字符减去字符0，而是先回答：输入“0”当然应得到0，那么空指针、空串、只有符号、夹杂字母或发生时也返回0，调用者如何知道这次转换是否成功？

作者的答案是“返回值加状态”：函数返回整数，同时用记录kValid或kInvalid。输入“+0”和“-0”返回0且状态有效；输入空串和“1a33”也返回0，但状态无效。这个才补全了接口语义。

输入返回值状态为何可区分
"0"0kValid数字完整消费
"+0"0kValid合法正号与数字
""0kInvalid没有数字
"+"0kInvalid符号后没有数字
"1a33"0kInvalid中途遇到非法字符
" 123"0kInvalid作者不跳过空白
"123 "0kInvalid作者不接受尾随字符
"2147483648"0kInvalid超出 int 范围
返回值 0 有两种含义，必须与状态一起读取，才能区分合法零与失败。

先预测四个输入。字符串“ 123”是否被接受？“123x”是否返回123？“+”是否等于0？“-2147483648”是否溢出？作者的答案依次是：无效、无效、无效、有效。现有页面原先实现的是跳过空白、读取数字前缀并在溢出时饱和，它与原书不是同一道契约。

先完成面试沟通，再写字符循环

第7章把本题作为完整案例，重点是“完整面试沟通与边界测试”。动手前应向面试官确认至少六项：

  1. 输入是否可能为nullptr，空字符串是否有效。
  2. 是否允许一个可选的正号或负号。
  3. 是否接受前导或尾随空白。
  4. 遇到非数字时是停止并返回前缀，还是让整串无效。
  5. 目标整数位宽是多少，越界时返回错误、饱和、抛异常还是采用其他协议。
  6. 合法整数0与失败如何区分，接口是否允许状态、布尔值或结果类型。

作者源码已经给出具体回答：目标是32位有符号int；允许一个开头符号；不接受任何空白或其他字符；必须消费完整字符串；越界和格式错误都返回0并置kInvalid。把每个字符都验证完才成功，称为。

事务式解析：默认无效，完整消费后提交有效1重置status=kInvalid不沿用上次状态2入口检查非空指针且非空串否则返回无效零3符号检查可选一个 + 或 -符号后必须有数字4数字核心每位必须 0…9负向累加防溢出5提交到达终止符完整消费才 kValid负向累加：num = num × 10 − digit，可直接表示 INT_MIN（-2147483648）而不溢出。越界（如 +2147483648、-2147483649）或非法字符（1a33）立即失败；作者不跳过空白。返回值 0 有“合法零”与“失败”两种含义，必须与全局状态 kValid/kInvalid 一起读取。
作者采用“默认无效，完整消费后提交有效”的事务式解析流程。

这套合同与标准atoi并不相同。atoi会做空白和前缀处理，而且无法通过返回值报告错误；现代可以返回结束指针与错误码，但调用者仍要检查结束指针是否到达字符串末尾，才能实现作者的全串语义。面试沟通的目的就是先冻结这些差异。

作者入口函数：默认失败，成功后再提交

StrToInt每次调用一开始先把g_nStatus设为kInvalid，并把num设为0。这一步非常关键：如果上一次解析成功而本次传入空指针，不能把旧的kValid留给新结果。

只有str非空且首字符不是终止符时才继续。入口消费可选的加号或减号，并用minus记录负号；消费符号后还要再次检查终止符，所以“+”和“-”不会进入数字核心。其余情况交给StrToIntCore。

#include <cstdio>
 
long long StrToIntCore(
    const char* digit, bool minus);
 
enum Status { kValid = 0, kInvalid };
int g_nStatus = kValid;
 
int StrToInt(const char* str) {
    g_nStatus = kInvalid;
    long long num = 0;
 
    if (str != nullptr && *str != '\0') {
        bool minus = false;
        if (*str == '+') {
            ++str;
        } else if (*str == '-') {
            ++str;
            minus = true;
        }
 
        if (*str != '\0')
            num = StrToIntCore(str, minus);
    }
 
    return static_cast<int>(num);
}
 
long long StrToIntCore(
    const char* digit, bool minus) {
    long long num = 0;
 
    while (*digit != '\0') {
        if (*digit >= '0' && *digit <= '9') {
            int flag = minus ? -1 : 1;
            num = num * 10
                + flag * (*digit - '0');
 
            if ((!minus && num > 0x7FFFFFFF)
                || (minus
                    && num
                       < static_cast<signed int>(
                           0x80000000))) {
                num = 0;
                break;
            }
            ++digit;
        } else {
            num = 0;
            break;
        }
    }
 
    if (*digit == '\0')
        g_nStatus = kValid;
    return num;
}

这段代码体现了一个可靠的：StrToIntCore只有在digit最终指向终止符时才设置kValid。非法字符与溢出都在指针尚未到末尾时break，因此状态保持无效。

这种“默认失败，末尾提交”的写法比在每条错误分支分别设置状态更稳。新增错误条件时，只需确保它不能越过提交点，便不会误报成功。时间复杂度是O(n)，额外空间O(1)。

为什么负数要沿负方向累加

作者每读到一位，都根据minus选择flag为1或-1：

正数：num = num × 10 + digit
负数：num = num × 10 - digit

直接把负数累计为负值称为。32位有符号范围并不对称：最大值是2147483647，最小值是-2147483648。若先把“-2147483648”的绝对值累计到正int，2147483648已经超出正上界；在long long中负向累计则可自然得到合法下界。

正数每轮更新后检查num是否大于0x7FFFFFFF；负数检查num是否低于作者期望的0x80000000有符号解释。这个保证加上越界位后马上失败，不会继续扫描。

作者先用long long承接累计值，再判断32位范围，因此首次越过int边界时long long仍足够容纳。不过源码把无符号十六进制常量0x80000000强制转成signed int，超出signed int正范围后的转换结果由实现定义；在作者使用的32位补码环境中得到INT_MIN，但可移植代码应直接使用INT_MIN或显式的固定宽度边界。

不是镜像

输入累加结果范围判断位置作者结果
+21474836472147483647不超过 INT_MAX0x7FFFFFFF有效
+21474836482147483648大于 INT_MAX上溢 1无效，返回 0
-2147483647-2147483647不低于 INT_MIN下界前 1有效
-2147483648-2147483648恰好等于 INT_MIN0x80000000有效
-2147483649-2147483649小于 INT_MIN下溢 1无效，返回 0
32 位有符号范围不对称；负向累加可以直接表示 INT_MIN。

“溢出”必须同时覆盖正向和负向。+2147483648只比INT_MAX大1，仍然无效；-2147483648恰好是INT_MIN，必须有效；-2147483649才是负向越界。只测试绝对值相同的正负数，容易错误拒绝最小值。

判断还必须发生在返回int之前。若先把越界long long强制转换为int，再判断结果，信息已经丢失。作者在long long里完成更新和边界比较，只有合法值或失败用的0才转换成int返回。

现代实现还可以在乘10之前预检。令limit在正数时为2147483647，在负数时为2147483648；若当前magnitude大于(limit减digit)除以10，则下一步必越界。这样即使目标边界扩展到long long，也不会让中间乘法先溢出。

现代显式结果接口

全局g_nStatus使调用者必须在下一次解析前立即读取状态，并且并发线程会相互覆盖，嵌套调用也可能污染结果。更清晰的接口把值和错误放进同一个返回对象，同时保留作者的严格全串规则。

#include <cstdint>
#include <limits>
#include <string_view>
 
enum class ParseError {
    none,
    empty,
    signOnly,
    invalidCharacter,
    outOfRange,
};
 
struct ParseIntResult {
    std::int32_t value;
    ParseError error;
    bool ok() const {
        return error == ParseError::none;
    }
};
 
ParseIntResult parseInt32(
    std::string_view text) {
    if (text.empty())
        return {0, ParseError::empty};
 
    std::size_t index = 0;
    bool minus = false;
    if (text[index] == '+'
        || text[index] == '-') {
        minus = text[index] == '-';
        ++index;
    }
    if (index == text.size())
        return {0, ParseError::signOnly};
 
    const std::uint64_t limit =
        minus ? 2147483648ULL
              : 2147483647ULL;
    std::uint64_t magnitude = 0;
 
    for (; index < text.size(); ++index) {
        const char ch = text[index];
        if (ch < '0' || ch > '9')
            return {
                0,
                ParseError::invalidCharacter,
            };
 
        const std::uint64_t digit =
            static_cast<unsigned>(ch - '0');
        if (magnitude
            > (limit - digit) / 10) {
            return {
                0,
                ParseError::outOfRange,
            };
        }
        magnitude = magnitude * 10 + digit;
    }
 
    if (minus
        && magnitude == 2147483648ULL) {
        return {
            std::numeric_limits<
                std::int32_t>::min(),
            ParseError::none,
        };
    }
 
    const auto positive =
        static_cast<std::int32_t>(magnitude);
    return {
        minus ? -positive : positive,
        ParseError::none,
    };
}

这个版本不跳过空白，也不接受数字前缀，仍与作者题意一致。它额外区分空输入、只有符号、非法字符和越界，返回对象没有共享可变状态，适合并发调用。string_view也把“空指针”排除在正常值域之外；若外部仍传C字符串，应在构造string_view前单独检查nullptr。

正负号与非法字符的精确行为

作者只允许首字符出现一次符号。“++1”“--1”“+-1”会在核心中遇到第二个符号，因此整串无效。前导零没有问题，“00012”逐位得到12；ASCII以外的全角数字也不是字符0到9，因而无效。

“正负号与非法字符”不是两个互不相关的分支。符号只由入口消费，核心函数因此能保持简单不变式：进入循环后的每个字符都必须是数字。任何破坏不变式的字符都把num清零并停止。

输入返回值状态为何可区分
"0"0kValid数字完整消费
"+0"0kValid合法正号与数字
""0kInvalid没有数字
"+"0kInvalid符号后没有数字
"1a33"0kInvalid中途遇到非法字符
" 123"0kInvalid作者不跳过空白
"123 "0kInvalid作者不接受尾随字符
"2147483648"0kInvalid超出 int 范围
返回值 0 有两种含义，必须与状态一起读取，才能区分合法零与失败。

作者的核心不会跳过空格，所以“ 123”和“123 ”都无效；也不会像部分解析器那样让“1a33”成功得到1。空指针、空串与只有符号甚至不会调用StrToIntCore，状态自然保持初始化的kInvalid。

需要注意测试外壳自身的可移植性：Test(nullptr)随后用printf的百分号s输出空指针。许多运行库会显示“(null)”，但C/C++标准并不保证把空指针传给百分号s安全。验证空指针分支时，应让测试代码单独打印标签，不能把测试框架的未定义行为误算到转换函数上。

复现作者16次调用

作者不是只给“123”一个样例，而是按输入分类连续调用16次Test。它们覆盖nullptr、空串、无符号正数、显式正负号、夹杂字母、正负零、最大值附近、最小值附近，以及只有符号。

这些样例围绕边界成组出现：2147483647与2147483648相邻，-2147483648与-2147483649相邻；+0与-0共同证明返回0不等于失败；“+”“-”共同证明消费符号后必须再检查是否有数字。

现代测试可以直接断言值与错误；忠实测试作者接口时，则要在每次StrToInt调用后立即断言g_nStatus，避免下一次调用覆盖它。

#include <cassert>
#include <climits>
 
void testAuthorContract() {
    assert(StrToInt("123") == 123);
    assert(g_nStatus == kValid);
 
    assert(StrToInt("+0") == 0);
    assert(g_nStatus == kValid);
 
    assert(StrToInt("1a33") == 0);
    assert(g_nStatus == kInvalid);
 
    assert(StrToInt(" 123") == 0);
    assert(g_nStatus == kInvalid);
 
    assert(StrToInt("+2147483647")
           == INT_MAX);
    assert(g_nStatus == kValid);
 
    assert(StrToInt("-2147483648")
           == INT_MIN);
    assert(g_nStatus == kValid);
 
    assert(StrToInt("+2147483648") == 0);
    assert(g_nStatus == kInvalid);
 
    assert(StrToInt("-") == 0);
    assert(g_nStatus == kInvalid);
}

还应补充作者未列出的多符号、前后空格、前导零、超长数字串和全角数字。若生产接口允许并发，再增加多线程交错测试，证明显式结果版不会像全局状态那样发生覆盖。

从需求到验证的完整路径

本章练习

练习

问题 1： 为什么空串和合法 "0" 都返回 0 时，必须额外用状态区分？

问题 2： 解释"负数沿负方向累加"如何统一处理溢出判断。

问题 3： 列出至少 3 类必须覆盖的边界输入。

本章回顾

  1. 把字符串转换成整数首先是协议题，其次才是字符累加题。
  2. 作者采用严格全串解析，不跳过空白、不接受尾随字符，也不做饱和截断。
  3. 每次调用先置kInvalid，只有指针走到字符串终止符才在提交点改为kValid。
  4. 返回0必须与状态一起读取，才能区分合法零与格式错误或溢出。
  5. 入口函数只消费一个可选正负号，核心循环只接收字符0到9。
  6. 负向累加自然表示-2147483648，体现32位有符号范围的不对称。
  7. 溢出守卫要在窄化为int之前执行，可移植实现应使用明确边界而非实现定义的强制转换。
  8. 全局状态不适合并发与嵌套调用，现代接口应把值和错误封装在同一结果中。
  9. 作者16次调用形成完整边界矩阵，测试时必须同时断言返回值和状态。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

状态码
记录转换是否有效的标志，如 g_nStatus 的 kValid/kInvalid，区分合法 0 与失败。
溢出
结果超出目标类型可表示范围，32 位有符号整数正界 2147483647、负界 -2147483648。
边界
输入或数值的极限情形，如空串、仅符号、正负最大值，决定解析正确性。
全串解析
必须消费完整输入字符串才返回成功，任何未消费字符都视为失败。
from_chars
C++17 字符转换函数，返回结束指针与错误码，仍需检查是否到达末尾。
atoi
C 标准库字符串转整数函数，做空白和前缀处理，但无法报告转换错误。
复习本章（5 题）

讨论

评论区加载中…