int溢出判断问题

博客起源

做力扣第7题和第8题这两道题时, 我找不到笔和草稿纸, ipad也不在, 于是就打算用latex语句来打草稿, 之后又花了不少时间把草稿变成一篇博客.

问题简述

long long res;
if (res * 10 + digit > INT_MAX) return INT_MAX;
// 这样判断溢出没有问题, 但如果res是int类型该怎么办呢?

问题分析

求下列不等式的等价判定条件\\
res \cdotp 10 + digit > \texttt{INT_MAX} = 2147483647  ①\\
res \cdotp 10 + digit > \texttt{INT_MAX} =  \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor \cdotp 10 + 7\\
(res - \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor)\cdotp10 > 7 - digit\\
现对res不同值进行分类讨论\\
如果res > \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor, ①式必然成立\\
如果res = \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor, digit=8或9时①式成立\\
如果res < \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor, ①式必然不成立\\
总结:res > \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor只是判断溢出的一个充分不必要条件, 而我们需要求充要条件.

一个特例

int res;
if (res > INT_MAX / 10) return INT_MAX; // 这个判断仅适用于力扣第7题,整数反转

在力扣第7题-整数反转中, 如果一个接近2147483647的数反转后要溢出, 那么反转后的数的最后一位只能是2, digit只能是2,不可能是8或者9, 所以在力扣第7题中可以用(res > INT_MAX / 10)代替(res * 10 + digit > INT_MAX)来判断溢出, 注意前者resint类型, 后者reslong long类型.

证明y总方法正确

int res;
if (sign > 0 && res > (INT_MAX - digit) / 10) return INT_MAX; // 这是acwing y总判断溢出的方法.

我一开始就想不通这为什么是正确的, 因为除以10会取整.

res > \lfloor\frac{\texttt{INT_MAX} - digit}{10}\rfloor   ②\\
res > \lfloor\frac{\lfloor\frac{\texttt{INT_MAX}}{10}\rfloor\cdotp10 + 7 - digit}{10}\rfloor \\
res > \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor + \lfloor \frac{7 - digit}{10} \rfloor\\
res -\lfloor\frac{\texttt{INT_MAX}}{10}\rfloor > \lfloor \frac{7 - digit}{10} \rfloor  = 0  (当digit <=7)\\
res -\lfloor\frac{\texttt{INT_MAX}}{10}\rfloor > \lfloor \frac{7 - digit}{10} \rfloor = -1  (当digit =8或9)\\

现对res不同值进行分类讨论, 注意①式的res是long long类型, ②式的res是int类型\\
如果res > \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor,  ②式成立, ①式也成立 \\
如果res = \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor,  digit=8或9时①式②式同时成立\\
如果res < \lfloor\frac{\texttt{INT_MAX}}{10}\rfloor,  ①式②式都不成立.\\
总结: 若res是int类型, res > \lfloor\frac{\texttt{INT_MAX} - digit}{10}\rfloor可以判断正溢出的.  y总的方法是正确的 orz.

程序验证

我写了一个简单暴力的程序来验证一下, 如果res2是long long类型(res2 * 10 + digit > INT_MAX)这个溢出判断显然很正确, 但如果res是int类型(res > (INT_MAX - digit)/10)这个溢出判断就让我困惑.

#include<iostream>
using namespace std;

int main() {
    long long res2;
    for (int res; res < INT_MAX; res ++)
    {
        res2 = res;
        for (int digit = 0; digit < 10; digit ++)
        {
            if (res2 * 10 + digit > INT_MAX != res > (INT_MAX - digit) / 10)
            {
                printf("you are wrong!\n");
                return 0;
            }
        }

    }
    printf("you are right!\n");
    return 0;
}

运行几十秒后, 程序输出right!, 再次证明y总的方法是对的. 负溢出的判断时一样的, 就不写证明和验证了.

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇