这篇文章是csapp第二章第三节的阅读笔记。

整数的运算包括加减乘除，对于每一种运算都涉及到有符号整数和无符号整数。

这里涉及到的符号：

1. 无符号整数加法

有两个w位的无符号整数x和y：$0 \leq x,y \leq 2^w$，那么两个数和的范围就是$0 \leq x+y \leq 2^{w+1}-2$。这个数是不能用w位二进制数表示的，需要w+1位才能表示。

因此，如果仍然使用w位来存储$x+y$的结果的话，就有可能对真正的值进行截断。我们使用符号$+_w^u$来表示截断后的结果，那么有：
$$
x+_w^uy=\begin{cases}
x+y,& \text{$x+y<2^w$ 正常}\
x+y-2^w,& \text{$2^w \leq x+y \leq 2^{w+1}$ 溢出}
\end{cases}
$$
其实，也就是对$2^w$取模：
$$
x+_w^uy=(x+y)\ mod\ 2^w
$$
既然有可能溢出，那么我们有办法检测溢出吗？

令$s=x+_w^uy$，如果$s<x$，那么就溢出了。

用代码表示：

int uadd_ok(unsigned x, unsigned y) {
    unsigned sum = x + y;
    return sum >= x;
}

没有溢出就返回1，有溢出就返回0。

上面的无符号加法就是一个模数加法，在模数加法中，有一个阿贝尔群（abelian group）的概念。这里有一个0元素，然后对于群中的元素$x$来说，都有一个对应的加法逆元$-_w^ux$，使得：$-_w^ux+_w^ux=0$。这样就有了一个无符号数取反的操作。

对于一个$x$：$0 \leq x <2^w$，取反操作如下：
$$
-_w^ux=\begin{cases}
x,&\text{$x=0$}\
2^w-x,&\text{$x>0$}
\end{cases}
$$
可以知道，无符号数中，只有0的加法逆元是它本身。

2. 补码加法

接下来看看补码加法。对于两个补码表示的有符号整数$x$和$y$：$-2^{w-1}\leq x,y\leq 2^{w-1}-1$，两个数的和$x+y$的取值范围就是$-2^w\leq x+y \leq 2^w-2$，同样不能使用w位来表示，需要w+1位。这样，当我们使用w位来表示的时候，就需要对其进行截断。令符号$x+_w^ty$表示截断后的结果，那么：
$$
x+_w^ty=\begin{cases}
x+y-2^w,&\text{$2^{w-1}\leq x+y$ 正溢出}\
x+y,&\text{$-2^{w-1}\leq x+y <2^{w-1}$ 正常}\
x+y+2^w,&\text{$x+y<-2^{w-1}$ 负溢出}
\end{cases}
$$
其实有符号整数加法和无符号整数加法的二进制形式是一样的，而计算机在做计算的时候也是不进行区分的。

所以有：
$$
x+w^ty=U2T_w[T2U_w(x)+_w^uT2U_w(y)]=U2T_w[(x{w-1}2^w+x+y_{w-1}2^w+y)\ mod\ 2^w]=U2T_w[(x+y)\ mod\ 2^w]
$$
像无符号加法一样，补码加法也有溢出，而且还有两种溢出：正溢出和负溢出。那么如何检测溢出呢？

令$s=x+_w^ty$：

如果$x>0$且$y>0$，但是$s\leq 0$，那么就是正溢出；

如果$x<0$且$y<0$，但是$s\geq 0$，那么就是负溢出。

使用代码来表示：

int tadd_ok(int x, int y) {
    int sum = x + y;
    int neg_over = x < 0 && y < 0 && sum >= 0;
    int pos_over = x >= 0 && y >= 0 && sum < 0;
    return !neg_over && !pos_over;
}

如果没有溢出就返回1，发生溢出就返回0。

3. 补码取反

和无符号加法一样，补码加法也有一个加法逆元的概念。对于一个$x$：$-2^{w-1}\leq x<2^{w-1}$，它的加法逆元就是：
$$
-_w^tx=\begin{cases}
-2^{w-1},&x=-2^{w-1}\
-x,&x>-2^{w-1}
\end{cases}
$$
所以$TMin_w$的加法逆元就是它本身。因此在补码加法中，加法逆元是其本身的有两个元素：0和$TMin_w$。

对于一个有符号数取反，在二进制表示的层面上有一个简便的方法（以4位为例）：

简单来说就是，“取反加一”。

4. 无符号整数乘法

两个无符号整数$x$和$y$：$0\leq x,y\leq 2^w-1$，它们的乘积$x\ast y$的取值范围是$0\leq x\ast y\leq (2^w-1)^2=2^{2w}-2^{w+1}+1$，需要使用2w位才能保存，如果使用w位保存的话就会截断。令$x\ast _w^uy$是截断后的结果，那么：
$$
x\ast _w^uy=(x\ast y)\ mod\ 2^w
$$

5. 补码乘法

两个有符号整数$x$和$y$：$-2^{w-1}\leq x,y\leq 2^{w-1}-1$，它们的乘积$x\ast y$的取值范围是$-2^{w-1}\cdot(2^{w-1}-1)=-2^{2w-2}+2^{w-1}\leq x\ast y\leq (-2^{w-1})^2=2^{2w-2}$。

同样如果使用w位表示的也需要截断。令$x\ast _w^ty$表示截断后的结果，那么：
$$
x\ast _w^ty=U2T_w((x\cdot y)\ mod\ 2^w)
$$
和加法一样，补码乘法与无符号乘法的二进制表示是一样的。

可以使用下面的代码来检测是否有溢出：

int tmult_ok(int x, int y) {
    int p = x\ast y;
    return !x || p/x == y;
}

没有溢出的话返回1，否则返回0。

如果不用除法的话可以这样：

int tmulk_ok(int x, int y) {
    int64_t pll = (int64_t) x\ast y;
    return pll == (int) pll;
}

首先使用64位的数保存两个32位数的乘积，这是能够完整保留结果的，然后将其截断到32位，看是否一致。如果一致说明没有溢出，否则就有溢出。

6. 乘以常数

计算机的乘法操作比较耗时，因此编译器会将乘法优化成移位操作和加减法。

不管是有符号还是无符号，左移一位，就相当于乘以2，那么左移k位，相当于乘以$2^k$。

所以无符号：$x<<k=x\ast _w^u2^k$；

有符号：$x<<k=x\ast _w^t2^k$。

同时，任何一个整数都可以写成多个2的幂次数的和的形式。比如$14=2^3+2^2+2^1$，所以乘以一个常数都可以转换成多个左移和加法操作：
$$
x\ast 14=(x<<3)+(x<<2)+(x<<1)
$$
一般来说，对于常量$K$，乘法$x\ast K$都可以表示成左移操作和加减法操作。对于$K$，可以表示成下面的二进制形式：
$$
[(0…0)(1…1)(0…0)\cdots(1…1)]
$$
比如14可以表示成$[(0…0)(111)(0)]$，令连续1的下标是$n$和$m$，且$n\leq m$，对于14来说$n=3,m=1$。

都可以表示成下面两种形式：

A：$(x<<n)+(x<<(n-1))+\cdots+(x<<m)$

B：$(x<<(n+1)-(x<<m))$

比如：
$$
x\ast 6=(x<<2)+(x<<1)\
x\ast 31=(x<<5)-x\
x\ast (-6)=(x<<1)-(x<<3)\
x\ast 55=(x<<6)-(x<<3)-x
$$

7. 除以2的幂

首先需要确定，整数除法是向0取整的。比如$5/2=2.5$，然后向0取整$\lfloor 2.5\rfloor=2$；比如$-12340/256=-48.203125$，然后向0取整$\lceil -48.203125\rceil=-48$。

左移1位是乘以2，右移应该就是除吧？但是右移操作有两种：逻辑右移和算术右移。

那么对于无符号数除以一个2的幂次数，就可以直接逻辑右移了。令$x’=x>>k$，那么就有：
$$
x’=\lfloor x/2^k\rfloor
$$
对于大于0的有符号数来说，也可以使用上面的方法进行计算；但是对于有符号数如果也使用向下取整的话，就会有问题了。从上面$-12340/256$的结果就可以看出来，如果向下取整的话结果是-49而不是-48。所以我们需要使用另外的方法来计算有符号数除以2的幂次数。

为了能够对于小于0的数的计算结果向上取整，需要加一个偏差值。根据$\lceil x/y\rceil=\lfloor (x+y-1)/y\rfloor$，可以这样：
$$
（x<0 ? x+(1<<k)-1:x)>>k
$$
来计算有符号整数除以2的幂次数的结果。

一个有意思的题目：写出div16()函数来计算x/16的值，其中x的类型是int，但是不使用比较运算符、除法运算符、取模运算符、条件判断、比较或循环：

int div16(int x) {
    int bias = (x >> 31) & 0xF;
    return (x + bias) >> 4;
}

8. 关于整数运算的思考

• 计算机执行整数运算其实是一种模运算形式；
• 有限字长限制了取值范围，导致计算结果可能溢出；
• 无论是补码还是无符号运算，底层的二进制行为是一致或非常类似的；
• unsigned类型会导致很多察觉不到的问题。