《CSAPP》整数运算（第二章）

整数运算

无符号加法

两个非负整数x和y，满足0<=x,y<=2^w，每个数都能表示为w位无符号数字。
无符号运算就是把整数和x+y截断为w位得到的结果，再把这个结果看做是一个无符号数。也可以看作一种形式的模运算。

原理：
当x+y<2^w，相加结果为x+y，属于正常情况
当2^w<=x+y<2^w+1，相加结果为x+y-2^w，属于溢出情况
算术运算溢出：
指完整的整数结果不能放到数据类型的字长限制中去，如上边的两个运算数的和为2^w或者更大时，就发生了溢出。
检测无符号数加法中的溢出：
对在范围内0<=x,y<=UMaxw中的x和y，令s是x+y的和，当且仅当s小于x（或者等价的s小于y）时，发生了溢出。

补码加法

给定在范围-2^w-1<=x,y<=2^w-1 -1之内的整数值x和y，他们的和就在范围-2^w<=x+y<=2^w -2之内，要想准确表示，可能需要w+1位。
定义补码加法x+y为整数和x+y被截断为w位的结果，并将这个结果看做是补码数。
原理：
当2^w-1<=x+y时，相加结果为x+y-2^w,属于正溢出情况（两个正数相加，得到一个负数）
当-2^w-1<=x+y<=2^w-1，相加结果为x+y，属于正常情况
当x+y<-2^w-1时，相加结果为x+y+2^w，属于负溢出情况（两个负数相加，得到一个非负的结果）
检测补码加法中的溢出
当两个大于0的数相加得到一个负数时，发生正溢出。
当两个小于0的数相加得到一个非负数时，发生负溢出。

补码的非

当x=TMinw时，补码的非等于TMinw。
当x>TMinw时，补码的非等于包括符号位，每位取反，最后一位加1，得到的结果。

无符号乘法

将一个无符号数截断为w位等价于计算该值模2^w。
原理：
对满足0<=x,y<=UMaxw的x和y有：x*y=(x*y)mod 2^w

补码乘法

先计算无符号乘法，再把无符号数转换为补码即可
原理：
x*y=U2Tw((x*y)mod 2^w)

乘以常数

编译器使用了一项重要的优化，用移位和加法运算的组合来代替乘以常数因子的乘法。
乘以2的幂
乘以2^k，就在该数的右边加k个0。相当于左移k位，对于其固定字长的乘法，把其高k位被丢弃。

除以2的幂

除以2的幂也可以用移位运算来实现，只不过用的是右移，无符号数和补码数分别使用逻辑移位和算术移位来达到目的。
无符号数：一定是逻辑右移。右移k位，在高位补0，没有实际意义。
补码数：向下舍入。当x>=0时，即为非负数时，效果与逻辑右移是一样的，对于负数来讲，如果需要舍入时，要进行向下舍入。例如：右移4位将会把-771.25向下舍入位-772。