整数运算也分为两种,无符号整数和有符号整数。
无符号加减法
无符号就是简单将两个二进制位相加。但是结果存在溢出的问题,即结果无法放到字长的限制中去。
如果字长是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,式子恒等。
tadd_ok的实现有些条件应该不是必要的:
int tadd_ok(int x, int y){
int result = x + y;
return !(!(x > 0 && y > 0 && result <= 0) || (x < 0 && y = 0));
}
在x > 0 && y > 0 时,x + y应该永远也不会等于0,所以 溢出的条件应为: (x > 0 && y > 0 && (x + y) < 0) || ( x < 0 && y = 0).