Last Updated: 2023-12-08 13:03:20 Friday
-- TOC --
在C语言中，整数默认为signed类型，unsigned类型反而需要特别申明，需要写出unsigned这个关键词或在literal数字后面使用U表示。不管是signed还是unsigned，两个整数相加，相减，相乘或相除，即整数之间的四则运算，都存在溢出（overflow）的可能，这是C代码需要特别注意和小心的地方！
当计算结果超过寄存器的bit位数后，CPU执行truncate，超过的bits直接被丢弃了，这是overflow问题稍微有点复杂的根源。首先，我们需要好好研究一下补码。
unsigned整数加减计算结果总是正数（也为unsigned类型），溢出的判断相对简单一些。
C语言层面，不方便直接读取rFlags寄存器，判断两个unsinged整数做减法计算的结果是否oveflow，可以很简单地直接比较unsigned数的大小。如果是加法，相加后的结果，如果小于某一个operand，即溢出。
判断unsigned整数加法溢出：
int check_unsigned_add_of(unsigned int a,
unsigned int b){
unsigned int c = a + b;
if(c<a || c<b)
return 1; // unsigned add overflow
return 0;
}
如果是减法，直接判断两unsigned的大小，小的减大的，overflow。
判断unsigned整数减法溢出：
int check_unsigned_sub_of(unsigned int a,
unsigned int b){
// a - b
if(a < b) // if((a-b)<0) is buggy!!
return 1; // unsigned sub overflow
return 0;
}
注意：当a小于b时，(a-b)<0是False，因为a和b都是unsigned，整个表达式会按照unsigned的方式来计算。
signed整数计算有两种不同的溢出，分别是positive overflow，和negative overflow。对于signed整数加法计算结果的判断，可以使用如下方法：
以上三条规则，与x86-64 CPU的OF标志位所表达的含义一致。
判断signed整数加法溢出：
int check_signed_add_of(int a, int b){
int c = a + b;
if((a>=0 && b>=0 && c<0) ||
(a<0 && b<0 && c>=0))
return 1; // signed add overflow
return 0;
}
判断signed整数减法是否溢出，就要反过来：
int check_signed_sub_of(int a, int b){
int c = a - b;
if((a>=0 && b<0 && c<0) ||
(a<0 && b>=0 && c>=0))
return 1; // signed sub overflow
return 0;
}
这个判断其实与加法判断是一样的，因为实际上是在计算c+b=a。
两个负数相加等于零的情况
只有在一种情况下，两个负数相加等于零，即当两个负数都为最大负数时。
#include <stdio.h>
int main(){
int a = 0x80000000;
int b = 0x80000000;
printf("%d\n", a+b);
return 0;
}
输出0！
最大负数还有一个坑：对它取绝对值无效！这个细节，请参考LeetCode第7题，反转整数，C/C++的实现。
绝不会溢出的情况
其实，0可以认为是正数，补码机制下，只有+0，这样可以简化以上表述。
加法都可能overflow，乘法当然更容易overflow了！
记住两个关于整数乘法的基本事实：
imul指令）假设用3bit补码来表达整数，3bit two's complement system:
3 --> 011
5 --> 101
-3 --> 101
做乘法：
unsigned: 5*3 = 15 --> 001111 （111:7）
signed: -3*3 = -9 --> 110111 （111:-1）
完整的bit表达不一样，但如果只看最末3位，总是一样的！
因此，判断是否overflow，就不需要区分signed和unsigned了。代码如下：
int check_mul_of(int x, int y){
int p = x * y;
return x && p/x!=y; // true means overflow
}
还有另外一种判断方法，用64位寄存器判断32位乘法：
int check_mul_of_2(int x, int y){
int64_t p = (int64_t)x * (int64_t)y;
return p != (int)p; // true means overflow
}
如果是计算64位的整数，就只能用第1种方法。
用最大负数除-1，在C语言中，这是个UB，Undefined Behavior！看编译器了，有时你的代码能得到“正确的”结果，即还是最大负数，有时就是Float Point Exception（FPE）。
要看汇编，除-1时，有时得到的汇编是：
neg eax
有时就是：
idiv ...
gcc编译在x64下的测试：
int main(){
int a = 0x80000000;
printf("%d\n", a/-1); // neg
int b = -1;
printf("%d\n", a/b); // idiv, SIGFPE
return 0;
}
因为最大负数没有对应的正数，除以-1的结果就是不对的。
因此，signed整数除法，需要判断除数，不能是0，或在最大负数时，还不能取-1！而unsigned除法，不可能除到-1，编译器会将其转换为unsigned后做整数除法，此时结果非0即1。
没有对潜在的整数计算溢出进行处理，或可能的异常进行规避，是很多软件Bug的原因之一！
设a和b为singed，a'和b'为unsigned，n为bit位数，
\(a'=a+a_{n-1}2^n\)，（\(a_{n-1}\)为a的MSB，0或1）
\(b'=b+b_{n-1}2^n\)，（\(b_{n-1}\)为b的MSB，0或1）
\(a'b'=ab+(ab_{n-1}+ba_{n-1})2^n+a_{n-1}b_{n-1}2^{2n}\)
此时，我们关注\(a'b'\)和\(ab\)的末n个bit位是否一样？对等号两边取模：
\(a'b'\mod 2^n=ab\mod 2^n\)，（\(2^n\)和\(2^{2n}\)这两项在模\(2^n\)时都为0）
证明结束！
补充信息
n个bit的signed整数x可以按补码表达为：
\(x=-x_{n-1}2^{n-1}+x_{n-2}2^{n-2}+...+x_02^0\)
bit表达不变时，unsigned的正整数y是这样的：
\(y=y_{n-1}2^{n-1}+y_{n-2}2^{n-2}+...+y_02^0\)
因此：\(y=x+x_{n-1}2^n\)
以上证明，a，b，ab均有可能是负数，取模时，是如何计算的？
这个问题反反复复的出现并困扰着我，至今没有找到权威的解答。这里仅仅是我个人目前的理解。
我认为Python中的对负数取一个正数模的计算是对的，而C语言的计算是错的（C语言计算存在负数时的模运算时，是有问题的，这个细节我在网络上也看到过说明）
>>> -16 % 8
0
>>> 15 % 8
7
>>> -9 % 8
7
首先观察到，负倍数的模为0，就对应了上述证明中取模后消掉的两项。
模数是一个正数，结果是余数，也应该是个整数，在0--模数-1这个范围内，这符合我们小学学习的竖式除法。只是负数取余数的现实含义违反直觉。这种计算，对于负数而言，也正好就是将其补码表达方式的高bit位抹掉，只留下低n位。或者说，将负数按照unsigned解释后进行模运算。
按照unsigned解释后做模运算，就是直接抹掉高bit位。
本文链接：https://cs.pynote.net/sf/c/202307088/
-- EOF --
-- MORE --