整数运算也分为两种，无符号整数和有符号整数。
无符号加减法
无符号就是简单将两个二进制位相加。但是结果存在溢出的问题，即结果无法放到字长的限制中去。
如果字长是w，则无符号数最大就是2的w次方减1，这就导致如果两个数的和如果到达2的w次方，结果实际上就少了2的w次方。比如字长为4，1001+1001，结果实际上是10010 - 10000 = 10。十进制来看就是9+9 = 9+9-16 = 2，结果里少了2的四次方。
检测无符号数加法的溢出，就是先让直接加起来两个数字，由于默认会丢掉最高位。所以取剩下的部分作为结果，再和任何一个加数比较，如果结果小于加数就发生了溢出。因此可以写一个判断程序：
2.27 判断是否溢出。
int uadd_ok(unsigned x, unsigned y){
unsigned result = x + y;
return result >= x;
}
减法就是对无符号数求反再加。对无符号数求反，就是简单的用2的字长次方减去无符号数，就可以得到结果
2.28 无符号数求反
| x |
对x按4字长取反 |
| 十六进制 |
十进制 |
十进制 |
十六进制 |
| 0 |
0 |
0 |
0 |
| 5 |
5 |
2的四次方-5 = 11 |
B |
| 8 |
8 |
2的四次方-8 = 8 |
8 |
| D |
13 |
2的四次方-13 = 3 |
3 |
| F |
15 |
2的四次方-15 = 1 |
1 |
补码加减法
补码加法的核心是，在底层的操作与无符号数是一样的。只是解释不同。
所以溢出存在，但是方向不同。由于无符号的溢出位置不影响原本的字长数，而补码中，实际的字长少了一位有效数字。
所以存在正溢出和负溢出。用两个大的int数相加，结果的最高位如果是1，溢出到了符号位，就变成负数，相当于从结果中减去2的字长次方。
反过来如果两个很大的负数相加，会发生负溢出，结果实际上被加上了2的字长次方。先来看正溢出的情况
int main()
{
//4d7c6d00
int i = 1300000000;
show_bytes((byte_pointer) &i, sizeof(int));
//59682f00
int j = 1500000000;
show_bytes((byte_pointer) &j, sizeof(int));
//a6e49c00
int sum = i + j;
show_bytes((byte_pointer) &sum, sizeof(int));
printf("%d + %d = %d\n", i, j, sum);
}
结果是1300000000 + 1500000000 = -1494967296，这个结果等于2800000000 - 4294967296（2的32次方）
负溢出的情况是：
int main()
{
//4d7c6d00
int i = -1300000000;
show_bytes((byte_pointer) &i, sizeof(int));
//59682f00
int j = -1500000000;
show_bytes((byte_pointer) &j, sizeof(int));
//a6e49c00
int sum = i + j;
show_bytes((byte_pointer) &sum, sizeof(int));
printf("%d + %d = %d\n", i, j, sum);
}
结果是-1300000000 + -1500000000 = 1494967296，很显然，结果是-2800000000 + 4294967296
检测补码溢出的方式是检测两个加数和结果，如果两个加数都大于0且和小于0，发生正溢出；两个加数都小于0且和大于0，发生负溢出。
2.29 补码的和
| x |
y |
x+y 整数和 |
x+y 补码和 |
情况 |
| 10100 |
10001 |
-27 |
5 |
负溢出 |
| 11000 |
11000 |
-16 |
-16 |
没有溢出 |
| 10111 |
01000 |
-1 |
-1 |
没有溢出 |
| 00010 |
00101 |
7 |
7 |
没有溢出 |
| 01100 |
00100 |
16 |
-16 |
正溢出 |
2.30 检测是否补码加法是否溢出的函数，直接按照判断标准写即可：
int tadd_ok(int x, int y){
int result = x + y;
return !(!(x > 0 && y > 0 && result <= 0) || (x < 0 && y < 0 && result >= 0));
}
2.31 代码纠错
int tadd_ok(int x, int y){
int sum = x + y;
return (sum - x == y) && (sum - y == x);
}
这个的关键在于sum之后的结果再减去x是否可以得到y。由于补码是一个循环的阿贝尔群，无论是否溢出，sum-x==y和sum-y==x永远返回true。所以这个函数的结果永远是true，也就起不到判断的作用。
2.32 代码纠错
用这个函数去判断x-y是否溢出可以吗？
int tsub_o(int x, int y){
return tadd_ok(x, -y);
}
看到减号就要想到补码的正负数不是一一对应的这个问题。在y等于int的下限的时候，-y就会出问题，依然和y相等，虽然从补码的底层逻辑来看是正确的，但从整数的角度来看，逻辑是错误的。
写这个函数的正确版本首先要区分y的取值范围。-2147483647=<y<=2147483647的时候，可以调用tadd_ok函数，但在y等于最小值的时候，直接通过判断x而不是y来返回结果。
int tsub_o(int x, int y){
if (y >= -2147483647) {
return tadd_ok(x, -y);
} else {
return x < 0;
}
}
测试该函数：
int main()
{
int x1 = 123;
int x2 = 0;
int x3 = -3908;
int y = -2147483647-1;
//x1 = 123 y = -2147483648，x1+y 不溢出，x1-y溢出
printf("%d + %d OK？ %d\n", x1, y, tadd_ok(x1, y));
printf("%d - %d OK? %d\n", x1, y, tsub_o(x1, y));
//x2=0 y = -2147483648，x2+y 不溢出，x2-y溢出
printf("%d + %d OK？ %d\n", x2, y, tadd_ok(x2, y));
printf("%d - %d OK? %d\n", x2, y, tsub_o(x2, y));
//x3=-3908 y = -2147483648，x3+y 溢出，x3-y不溢出
printf("%d + %d OK？ %d\n", x3, y, tadd_ok(x3, y));
printf("%d - %d OK? %d\n", x3, y, tsub_o(x3, y));
}
这题一开始做的有点懵逼，就是-y=y把自己绕进去了。
补码的减法也就是取逆，其实很简单，由于正负数是不对称的，上边也看到了2.32的题目。所以当x为int下限的时候，-x就是x，也就是加法的逆。 其他情况就是直接取负即可。
2.33 字长为4的补码取逆
| x |
-x |
| 十六进制 |
十进制 |
十进制 |
十六进制 |
| 0 |
0 |
0 |
0 |
| 5 |
5 |
-5 |
B |
| 8 |
-8 |
-8 |
8 |
| D |
-3 |
3 |
3 |
| F |
-1 |
1 |
1 |
取一个补码表示的数的补码，除了各个位取补再加1之外，还有一个好办法是找到最右边的1，然后把这个1左边的所有位取反。
无符号和补码乘法
两个为什么放一起，是因为两者的底层操作完全相同。而且最后被截断的位也完全相同，只是解释不同。
2.34 字长3位的乘法
无符号整数的相乘，是直接用位相乘得到结果即可。补码相乘不是直接用位乘，而是先运算得到实际结果，再转换成二进制结果。
| 模式 |
x |
y |
x乘以y |
截断之后的x乘以y |
| 无符号 |
100 |
101 |
010100 |
20 |
100 |
4 |
| 补码 |
100 |
101 |
001100 |
12 |
100 |
-4 |
| 无符号 |
010 |
111 |
001110 |
14 |
110 |
6 |
| 补码 |
010 |
111 |
111110 |
-2 |
110 |
-2 |
| 无符号 |
110 |
110 |
100100 |
36 |
100 |
4 |
| 补码 |
110 |
110 |
000100 |
4 |
100 |
-4 |
2.35 这个证明没能力做出来，但是代码可以记住，判断x乘以y是否溢出的代码：
2.36 使用int64_t来判断是否溢出。
思路是先将两个int转换成64位，相乘之后，判断高位是否有数字，简单的方法就是转成32位然后判断值是否相等。如果高位全部是1表示负数或者是0，则结果相等表示没有溢出。否则数值会有变化。
int tmult_ok64(int x, int y){
__int64 result = (__int64) x * (__int64) y;
return result == (int) result;
}
2.37 修改XDR库函数的溢出错误。
原来函数的核心错误是malloc的参数类型 size_t 只有32位，而数组长度乘以每个元素的大小的乘积可能会导致溢出。
即使使用64位无符号整数：
uint64_t asize = ele_cnt * （uint64_t) ele_size
这句话会把ele_size转成64位无符号，ele_cnt也会转成64位无符号，然而如果溢出存在，在传给malloc函数的时候，依然会被截断成低32位。
解决方法想了半天，后来看答案才恍然大悟，32位字长之下，由于寻址限制，malloc根本没有必要分配超过32位的内存数量。
所以就用之前的判断溢出函数判断一下乘积是否溢出，如果溢出就返回NULL，不溢出，再交给malloc函数进行工作。
乘以常数的优化
刚才普通的乘法是模拟两个变量相乘。在实际乘法中，如果乘以常数，编译器通常不会直接采用乘法，而是采用移位和乘法相结合的方式。
乘以2的幂，无论是无符号还是补码形式，都可以采取移位运算，之后即使溢出，其结果也和执行普通的乘法是一样的。
换算成2进制的话，如果一个的位数某一个位有一个1，乘以这个数就相当于移位这个1后边的几个0。
比如 110 * 100, 100的第三位有一个1，则相当于把110右移100后边的两位。
2.38 汇编指令的LEA就是移位然后加上一个数字，可以执行(x<<k)+b这样的命令。
在k = 0，1,2,3和b=0或者x的情况下，可以表示的a的倍数如下：
| k |
b |
倍数 |
| 0 |
0 |
1 即还是原来的x |
| 1 |
0 |
2 |
| 2 |
0 |
4 |
| 3 |
0 |
8 |
| 0 |
x |
2 |
| 1 |
x |
3 |
| 2 |
x |
5 |
| 3 |
x |
9 |
综合起来看，可以表示1,2,3,4,5,8,9的倍数。
2.40
用移位来计算乘法:
- 由于6=4+2，一个数x乘以6 = (x<<1) + (x<<2)
- 由于31 = 32 - 1，一个数x乘以32 = x<<5 - x
- -6 = 2 - 8，所以是 (x<<1) - (x<<3)
- 55 = 32 + 16 + 8 - 1，所以是 (x<<5）+(x<<4)+(x<<3) - x,观察(x<<5）+(x<<4)+(x<<3)可以改写成 (x<<6) - (x<<3)的情况，所以最后是(x<<6) - (x<<3) - x
无符号和补码除法
整数的除法得到的结果是整数，相当于用竖式计算的时候得到的整数结果，抛弃余数。计算机除法的一个主要问题是留下的整数到底该往何处舍去。
对于无符号除以2的幂，由于无符号表示的都是非负数，可以采用将无符号数向右移的方法来除。而且结果也是一个整数，并且是向0舍入，所以结果是正确的。
但是补码除法就有一些问题了。在补码表示正数的时候，和无符号一样没有问题。但是在补码表示负数的时候，右移的时候高位会补1，在无法整除的情况下，结果会向负无穷舍入，而不是0。
举例子来说，如果只是用移位来解决问题。则 12340/16 = 771 ，而-12340/16 = -772，而这种结果是不可接受的，两个结果应该除了符号之外，整数的值相同。
所以才去的方法是给进行除法之前的数字加上一个偏置量，假如一个数字要除以2的k次幂，这个偏置量是(1<<k)-1，在如此操作之后，移位的结果就会向0的方向舍入，而不是向负无穷的方向。
所以补码除以2的幂的表达式就是 (x<0? x+(1<<k)-1: x) >> k
2.42 编写一个除以16的函数
不能使用任何除了移位和加减之外的方法。其实这就是把上边一个计算的规律写成函数，由于不能直接判断x是否大于0，则可以取x的最高位，然后替换公式里的结果：
int div16(int x){
//向右移31位，然后用掩码来获取最低位，也就是参数的最高位，这一位代表是不是负数
int highest_bit = (int) (0x00000001U & ((unsigned int) x) >> 15U);
//16是2的四次方
//用是不是负数来参与运算
return (x + (highest_bit << 4U) - highest_bit) >> 4;
}
2.43 猜数字
这个首先要看机器产生了什么结果，然后来猜数字。
可以看到先把x左移5位，然后再减去x，可以知道结果是 2的5次方-1 = 31，即M= 31
再来看y，如果y小于0，则y加上7，然后右移3位。从前边的公式可以知道，k=3，偏置量是x + 1<<3 -1 正好是7，所以这个结果是y/8,即N=8
2.44 判断公式
- (x>0)|| (x-1)<0， 这个意思就是x大于0或者x-1小于0。考虑x为int下限的结果，x大于0为假，x-1的结果是+2147483647，此时两个条件都为假。所以当x为int下限的时候不成立。
- (x&7)!=7 || (x<<29<0)。 x&7的结果是只保留最后3位，左边成真的条件是不等于7，也就是后三位不是111。右边的结果是x右移29位之后最高位是1。令左边为真的数只有000-110六种，令右边成真的只有100，101,110三种。左边取值范围覆盖右边，所以恒为真。
- (x * x) >= 0，这个早已经讨论过，如果两个数相乘发生溢出，最高位被截取到1，则就不会大于0。在x = 46341的时候就会发生溢出。
- x<0 || -x <=0。很显然。这个在除了下限之外的结果都是成立的。如果x等于下限，x的负数还是自己，所以也成立，这个式子恒为真。
- x>0 || -x >=0。当x为下限的时候，-x还是x，所以两边都是假。当x为下限的时候这个式子不成立。
- x + y = ux + uy，由于位级操作相同，且都要转换成无符号数进行比较，所以为真。
- x * ~y + uy * ux == -x，这个从数值取反来看，由于底层位不变，计算完之后转换成无符号数字，则相当于ux * (0x11111111),在转换成int，式子恒等。
