信息的表示和处理（3）：整数运算

2019-02-11 本文已影响0人月月月月_bd25

1.1 无符号加法

无符号加法定义

正常情况下, x+y的值保持不变。溢出情况下，x+y的值是该和减去 $2^\omega$ 的结果。
将x+y的操作看做是其和截断为 $\omega$ 位的结果。当x+y为正常情况时，和的最高位会等于0，丢弃最高位不会改变其数值。当x+y为溢出情况时，和的 $\omega + 1$ 位表示中的最高位会等于1，丢弃最高位就相当于从和中减去了 $2^\omega$
算术运算溢出的定义：指完整的整数结果不能放到数据类型的字长限制中去

检测无符号加法的溢出

无符号加法溢出的定义及推导

说白了，就是两个无符号数相加的和小于任意一个加数时，即可判定为溢出。

无符号数求反

加法逆元的定义：对每个值x，存在某个值y，使得两者执行无符号加法时，其和为0，则y为x的加法逆元，即x求反得y。数学定义如下：

无符号数求反的定义

1.2 补码加法

补码加法的定义

补码加法的定义图示

检测补码加法中的溢出

检测补码加法的溢出

1.3 补码的非

补码非的定义

事实上，求一个补码的非，可以通过对位级表示求补码非。

包括符号位，对补码x的每一位取反，然后对结果加1。如求-4的补码非，补码表示为1100，取反得0011，再加1得0100，即得其补码非的值为4。
对位向量x寻找最右边的1的位置k，然后对位置k左边的的所有位取反（不包括第k位），即可得到补码非。如-4，补码表示为1100，最右边的1 的位置为3，则从右往左数第4位开始的所有位取反，得0100，即得-4的补码非的值为4。

1.4 无符号乘法和补码乘法

无符号乘法：

无符号乘法的定义

x * y的结果可能需要 $2^\omega$ 位来表示。因此无符号乘法的值等价于将其值截断为 $\omega$ 位，即计算该值模 $2^\omega$ 。

补码乘法：

补码乘法的定义

补码乘法和无符号乘法的位级表示认为是一样的。因此有了如下性质：

无符号和补码乘法的位级等价性

也就是说，以十进制为例，求两个数（两者均为 $\omega$ 位的位表示）的乘积时，先按整数运算计算出乘积的值，然后将该值用对应的位表示（ $2^\omega$ 位）出来，此时无符号数和补码的乘积的位表示可能会不一样，但是截断为 $\omega$ 位后的位表示是一样的。具体例子如下：

3位数的无符号和补码乘法示例

1.5 常数乘除

乘以2的幂

乘以2的幂的原理

将无符号整数x乘以2的k次幂，即将x的位模式表示左移k位。若固定字长，则将其高k位丢弃。
左移一个数值等价于执行一个与2的幂相乘的无符号乘法。
固定大小 的补码算术运算的位级操作与其无符号运算等价，所以上述的乘法运算同样适用于补码乘法。注意，只有固定大小的算术运算才会得到相同的结果（因为算术结果的符号位被丢弃了，所以无符号数和补码乘法的结果拥有相同的位表示）

乘以常数

比如14的位模式为1110，则n=3，m=1，14*x的形式A为(x<<3)+(x<<2)+(x<<1)，形式B为(x<<4)-(x<<1)。

除以2的幂

补码除法-向下舍入

补码除法-向上舍入

补码除法-偏置技术

对于无符号数以及补码值x大于等于0的情况，除以2的幂相当于执行算术右移，且结果向下舍入。
对于补码值x为负数的情况，除以2的幂的结果应该向上舍入，直接应用算术右移将会得到向下舍入的结果，因此需要用偏置技术做调整。
偏置技术的意思是在算术右移前加上一个适当的偏置量，使其结果满足向上舍入。
除以2 的幂可通过逻辑或算术右移实现。但是这种方法不能推广到一般的常数。