csapp笔记——2.3节整数运算
无符号加法对于https://latex.csdn.net/eq?0%5Cleqslant%20x%2Cy%3C%202%5Ew的整数x,y，界说https://latex.csdn.net/eq?x+_%7Bw%7D%5E%7Bu%7Dy表示将x与y的和截为w位
https://latex.csdn.net/eq?x+_%7Bw%7D%5E%7Bu%7Dy%3D%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20x+y%2C%20x+y%3C2%5Ew%20%5C%5C%20x+y-2%5Ew%20%2C2%5Ew%5Cleqslant%20x+y%3C2%5E%7Bw+1%7D%20%5Cend%7Bmatrix%7D%5Cright.
由此推得检测无符号加法是否溢出得方法是判断结果是否比x，y中的任何一个小。
无符号数的逆元界说为使得https://latex.csdn.net/eq?x%20+_%7Bw%7D%5E%7Bu%7D%20y%20%3D0的y，若x为0则y为0，否则，y为https://latex.csdn.net/eq?2%5Ew-x
补码加法
对于https://latex.csdn.net/eq?-2%5E%7Bw-1%7D%5Cleqslant%20x%2Cy%3C2%5E%7Bw-1%7D的整数x,y，界说https://latex.csdn.net/eq?x+_%7Bw%7D%5E%7Bt%7Dy表示将x与y的和截为w位
https://i-blog.csdnimg.cn/direct/876fde36ba614721922e1cdb621004f5.png
https://i-blog.csdnimg.cn/direct/43b6c2d8424b4177ac3507f27f039ebf.png
检测溢出
https://i-blog.csdnimg.cn/direct/6cb8a66ff97148c29ee6e2bfeb10f2e6.png
这里留意，模数加法形成阿贝尔群，也就是补码加法和无符号数加法满足交换律，那么不管是否存在溢出，(x+y)-x总会即是y。
补码的非
https://i-blog.csdnimg.cn/direct/cf36a8e4568346168504958353615d66.png
对于一个给定的位级表示，无论把他视为补码照旧无符号数，其非的位级表示都是雷同的。
在C语言中对于任意整数x，~x+1就是它的非
可以这么理解：
https://latex.csdn.net/eq?~x+x=，以是~x+x+1=。
由此还可推得对于任意一个非零位级表示（只要x非零，必有一位是1）https://latex.csdn.net/eq?%5Bx_%7Bw-1%7D%2C...%2Cx_%7Bk%7D%2C1%2C0%2C...%2C0%5D（这里的1表示从右往左数第一个1）,对1左边的所有位取反就能得到其非。
无符号乘法
https://i-blog.csdnimg.cn/direct/73045c72fed44994931b3572fad60e59.png
补码乘法
先给出一个结论，对于给定的两个位级表示，将其视作无符号数相乘或者补码相乘，截断后的终极结果是雷同的。
以是对于补码乘法，可先将其视作无符号数相乘，得到相乘结果后再截断，将截断后的位级表示作为补码表明。
https://i-blog.csdnimg.cn/direct/491ad9d6080f41afbcaae7ec162f05a6.png
int32_t tmult_ok(int32_t x, int32_t y)
{
int32_t p = x * y;
return !x || p / x == y;
} 可用这段代码检测32位整数相乘是否溢出。
乘以常数
乘法指令的速率比其他整数运算要慢，编译器每每会实验用移位和加减法的组合来代替乘以常数的乘法。
对于补码和无符号数来说，左移k位都代表乘https://latex.csdn.net/eq?2%5Ek，对于一样平常的常数，编译器会将其分解为多少个2的次幂相加或者两个二的次幂相减，实际应用时可能既有相加又有相减，具体如下：
对于一个正数来说，[(0...0)(1...1)(0...0)(0...0)(1...1)...(1...1)]是他的位级表示，可能会有多少段连续的1，对于某一段连续的1来说，假设该段最高位是从团体最低位往左数第n个，最低位是从团体最低位往左数第k个，有两种方式表示
第一种
https://latex.csdn.net/eq?2%5E%7Bn-1%7D%20+%20...%20+%202%5E%7Bk-1%7D
第二种
https://latex.csdn.net/eq?2%5E%7Bn%7D%20-%202%5E%7Bk-1%7D
对这一段就可以使用左移
除以2的幂
大多数呆板上，除法比乘法更慢。但除法并不能像乘法一样分解为加减法，只能对常数为2的次幂的情况举行移位。
对于无符号数和补码的整数除法，我们希望会得到，一个向0取整的结果，对无符号数和大于零的补码来说，向右移k位相当于除以https://latex.csdn.net/eq?2%5Ek，结果恰恰是我们期望的向0取整。
对于小于零的补码，如此操纵依然会得到向下取整的结果，这就不符合我们的预期。因此需要做出调整。
整数除法有如下特性
https://latex.csdn.net/eq?%5Cleft%20%5Clfloor%20x/y%20%5Cright%20%5Crfloor%20%3D%20%5Cleft%20%5Clceil%20%28x-1+y%29%20/%20y%5Cright%20%5Crceil
我们希望负数除法时能向0取整，也就是向上取整。
因此对于负数补码，只需计算https://latex.csdn.net/eq?%5Cleft%20%5Clceil%20%28x-1+y%29%20/%20y%5Cright%20%5Crceil，当y为2的次幂时，计算https://latex.csdn.net/eq?%28x%20+%20%281%3C%3Ck%29-1%20%29%3E%3Ek即可。
附上例子，该函数可实现32位整数除以16
int div16(int32_t x)
{
int tmp = (x >> 31) & 0xf;
return (x + tmp) >> 4;
} 对于正数x，tmp为0，对于负数x，x>>31后得到的位级表示为全1，与0xf相与可得到低四位的值，也就是15.
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]