csapp笔记——2.3节整数运算

无符号加法

对于

的整数x,y，界说

表示将x与y的和截为w位

由此推得检测无符号加法是否溢出得方法是判断结果是否比x，y中的任何一个小。
无符号数的逆元界说为使得

的y，若x为0则y为0，否则，y为

补码加法

对于

的整数x,y，界说

表示将x与y的和截为w位

 检测溢出

这里留意，模数加法形成阿贝尔群，也就是补码加法和无符号数加法满足交换律，那么不管是否存在溢出，(x+y)-x总会即是y。

补码的非

对于一个给定的位级表示，无论把他视为补码照旧无符号数，其非的位级表示都是雷同的。
在C语言中对于任意整数x，~x+1就是它的非
可以这么理解：

~x+x=[1...1]，以是~x+x+1=[0...0]。
由此还可推得对于任意一个非零位级表示（只要x非零，必有一位是1）

（这里的1表示从右往左数第一个1）,对1左边的所有位取反就能得到其非。
无符号乘法

补码乘法

先给出一个结论，对于给定的两个位级表示，将其视作无符号数相乘或者补码相乘，截断后的终极结果是雷同的。
以是对于补码乘法，可先将其视作无符号数相乘，得到相乘结果后再截断，将截断后的位级表示作为补码表明。

1. int32_t tmult_ok(int32_t x, int32_t y)
2. {
3.         int32_t p = x * y;
4.         return !x || p / x == y;
5. }

复制代码

可用这段代码检测32位整数相乘是否溢出。
乘以常数

乘法指令的速率比其他整数运算要慢，编译器每每会实验用移位和加减法的组合来代替乘以常数的乘法。
对于补码和无符号数来说，左移k位都代表乘

，对于一样平常的常数，编译器会将其分解为多少个2的次幂相加或者两个二的次幂相减，实际应用时可能既有相加又有相减，具体如下：
对于一个正数来说，[(0...0)(1...1)(0...0)(0...0)(1...1)...(1...1)]是他的位级表示，可能会有多少段连续的1，对于某一段连续的1来说，假设该段最高位是从团体最低位往左数第n个，最低位是从团体最低位往左数第k个，有两种方式表示
第一种

第二种

对这一段就可以使用左移
除以2的幂

大多数呆板上，除法比乘法更慢。但除法并不能像乘法一样分解为加减法，只能对常数为2的次幂的情况举行移位。
对于无符号数和补码的整数除法，我们希望会得到，一个向0取整的结果，对无符号数和大于零的补码来说，向右移k位相当于除以

，结果恰恰是我们期望的向0取整。
对于小于零的补码，如此操纵依然会得到向下取整的结果，这就不符合我们的预期。因此需要做出调整。
整数除法有如下特性

我们希望负数除法时能向0取整，也就是向上取整。
因此对于负数补码，只需计算

，当y为2的次幂时，计算

即可。
附上例子，该函数可实现32位整数除以16

1. int div16(int32_t x)
2. {
3.         int tmp = (x >> 31) & 0xf;
4.         return (x + tmp) >> 4;
5. }

复制代码

对于正数x，tmp为0，对于负数x，x>>31后得到的位级表示为全1，与0xf相与可得到低四位的值，也就是15.

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。