V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
KyL
V2EX  ›  程序员

如何实现一个健壮的 atoi?

  •  
  •   KyL · 2016-02-24 22:17:42 +08:00 · 3239 次点击
    这是一个创建于 2955 天前的主题,其中的信息可能已经有所发展或是发生改变。

    处理正负号、非法字符什么的就不说了。
    将字符串转换为符号整型的过程中如何处理整型溢出呢?我 google 了一下,没找到什么相关的。

    14 条回复    2016-02-25 14:34:02 +08:00
    SoloCompany
        1
    SoloCompany  
       2016-02-24 23:06:42 +08:00   ❤️ 1
    其实没多复杂
    你每多处理一位(乘以 10 ( radix )再加上数字),就判断一次是否有溢出就是了

    因为乘法会溢出,除法不会
    所以,一般的做法,是在做乘法之前,估算是否有溢出,
    以最常见的 radix=10 ,无符号整数举例,安全值就是 (2^32 - 1)/10 ~ (2^32-10)/10 之间,对应的余数为 0~9
    这个安全值是固定的,只需要计算一次
    然后在你每次做乘法之前先检查是否小于安全值就知道有没有溢出了
    SoloCompany
        2
    SoloCompany  
       2016-02-24 23:07:51 +08:00
    修正一下,无符号整数距离应该是 2^31 不是 32 ,另外,对于负数,因为区间不一样,安全值要相应修正,但原理是一样的
    ChiChou
        3
    ChiChou  
       2016-02-24 23:21:07 +08:00
    难道楼主是看了 leetcode 的那题(逃
    iProxier
        4
    iProxier  
       2016-02-24 23:28:11 +08:00
    看看 Golang 的源代码
    zhjits
        5
    zhjits  
       2016-02-24 23:32:18 +08:00   ❤️ 1



    《 The Standard C Library 》 by P.J. Plauger
    congeec
        6
    congeec  
       2016-02-24 23:34:42 +08:00
    @zhjits glibc 里的么?
    zhjits
        7
    zhjits  
       2016-02-24 23:36:03 +08:00
    @congeec 那本书里面的参考实现。
    congeec
        8
    congeec  
       2016-02-24 23:45:23 +08:00
    @zhjits .....问的就是这本书里的代码哪儿来的....
    FUCKEX2
        9
    FUCKEX2  
       2016-02-24 23:49:40 +08:00
    用 boost 中的库 一句话搞定

    lexical_cast<double>(string);
    bcxx
        10
    bcxx  
       2016-02-24 23:56:37 +08:00
    https://github.com/rofl0r/musl/blob/master/src/stdlib/atoi.c 这样?貌似 manpage 里面也没有说溢出的处理情况吧?
    zhjits
        11
    zhjits  
       2016-02-24 23:58:24 +08:00
    @congeec 作者自己写的
    bcxx
        12
    bcxx  
       2016-02-25 00:05:12 +08:00   ❤️ 1
    但其实 glibc 里面的 atoi 是用 strtol 实现的…… 这个就有溢出处理了 http://fossies.org/dox/glibc-2.23/stdlib_2strtol__l_8c_source.html
    KyL
        13
    KyL  
    OP
       2016-02-25 11:23:53 +08:00 via Android
    @ChiChou 我曾经在面试中被问到过,在 leetcode 中也看到过,在写程序中也遇到过。但是奇怪的是,似乎没有人提到过处理整型溢出问题,在网上搜索的所有 atoi 实现,都没有,连提到都没有。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   942 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 20:55 · PVG 04:55 · LAX 13:55 · JFK 16:55
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.