博客起源
做力扣第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)
来判断溢出, 注意前者res
是int
类型, 后者res
是long 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总的方法是对的. 负溢出的判断时一样的, 就不写证明和验证了.