本文是 《CSAPP》第二章 - 信息的表示和处理 整数表示和运算部分的笔记。
1. 信息存储
- 字长：指针数据的标准大小，给定了虚拟地址空间的编码范围，也即虚拟地址空间的大小。
- 字节顺序：一旦选择了操作系统，字节序也就确定下来
- 小端法：Intel，Android，IOS（虽然ARM能够配置使用大端法或者小端法，但是os只能运行于小端模式）
- 大端法：Oracle，IBM的大型机
- 需要注意字节顺序的地方：
- 通过网络传递二进制数据
- 阅读表示整数数据的字节序列，例如反汇编器生成的数据
- 通过强制类型转换规避类型系统的时候
- 字符表示
man ascii可以显示ASCII码表- 十进制数字a的ASCII码表示是
0x3a
- 代码表示
- ABI：某个特定体系结构下两层软件（例如libc和Linux内核）间二进制层面的交互接口。例如，Linux ABI。
- c语言位级运算：位向量可以表示有限集合
&: 与，对应集合的交|: 或，对应集合的并~: 取反，对应集合的补^: 异或，和1异或是取补，和0异或不变
- c语言逻辑运算：对应命题逻辑
||: 逻辑或&&: 逻辑与!: 逻辑非- 和位级运算的一些区别
- 逻辑运算认为所有非零参数都表示TRUE，参数0表示FALSE
- 逻辑运算具有短路效应
- c语言移位运算
- 一般而言，对有符号数使用算术右移，对无符号数必须使用逻辑右移，和c不同的是，Java对于如何移位有明确的定义
- 对于一个由w位组成的数据类型，如果要移动k>=w位
- c语言标准没有明确定义（UB），但是机器上一般会移动
k mode w位 - Java明确定义会移动
k mod w位
- c语言标准没有明确定义（UB），但是机器上一般会移动
2. 整数的表示
位向量对应二进制表示
- 整数数据类型：典型情况下
- int类型在32位和64位下均为4字节
- long类型在32位下为4字节，64位下为8字节
- 无符号数的编码：
- 对向量$x = [x_{w-1}, x_{w-2}, …, x_0]$，$B2U_w = \sum_{i=0}^{w-1}x_i2^i$
- 无符号数编码具有唯一性，即二进制数转无符号数是一个双射
- 有符号数的补码表示：
- 对向量 $x = [x_{w-1}, x_{w-2}, …, x_0]$, $B2T_w(x) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}2^i$
- 该定义和无符号数的区别在于最高有效位的权值
- 有符号数编码具有唯一性，即二进制数转有符号数是一个双射
- 对向量 $x = [x_{w-1}, x_{w-2}, …, x_0]$, $B2T_w(x) = -x_{w-1}2^{w-1} + \sum_{i=0}^{w-2}2^i$
- 一些事实
- 4字节无符号数最大值约为$4 * 10^9$
- 4字节有符号数最大/最小值约为$\pm2*10^9$
- 补码范围有不对称性：最小值的绝对值是最大值加1
- 最大无符号值是有符号值的两倍加1
2.1. 有符号和无符号数间转换
- 对同样字长的值，C语言的强制类型转换不改变位模式
- 补码转换为无符号数：对$TMin_w \le x \le TMax_w$
- $x \ge 0, T2U_w(x) = x$
- $x < 0, T2U_w(x) = 2^w + x$
- 核心在于考虑位模式，证明只用关注最高位权重的变化即可，负数转换位无符号时，最高位权值从-1变为+1，即加上两个$2^{w-1}$，其余位权值不变
- 无符号数转换为补码: 对$0 \le x \le UMax_w$
- $x \le TMax, U2T_w(x) = x$
- $x > TMax, U2T_w(x) = x - 2^w$
- 核心在于考虑位模式，证明只用关注最高位权重的变化即可，负数转换位无符号时，最高位权值从-1变为+1，即减去两个$2^{w-1}$，其余位权值不变
C语言中有符号和无符号
- 当一种类型的表达式被赋给另一种类型的变量时，转换是隐式发生的
- 当执行运算时，如果一个运算数是有符号的而另一个是无符号的，则C语言会隐式将有符号转换为无符号
- 例如：
-1 < 0u，返回是0
- 例如：
- TMIN的写法
-TMAX - 1- 不能用字面量表示，
-2147483648中-是单目运算符，字面量使用2147483648会溢出。
2.2. 扩展和截断
- 无符号数的零扩展
- 定义宽度分别为w和w’的位向量$x = [x_{w-1}, x_{w-2}, …, x_0], x’ = [0, …, x_{w-1}, x_{w-2}, …, x_0]$，且$w’ > w$，则有$B2U_w(x) = B2U_{w’}(x’)$
- 补码数的符号扩展
- 定义宽度分别为w和w’的位向量$x = [x_{w-1}, x_{w-2}, …, x_0], x’ = [x_{w-1}, x_{w-1}, …, x0]$，且$w’ > w$，则有$B2T_w(x) = B2T_{w’}(x’)$
- 无符号数的截断
- 定义宽度为w的位向量$x$，截断k位后为$x’$，则有$B2U(x’) = B2U(x)\;mod\;2^k$
- 补码数值的截断
- 定义宽度为w的位向量$x$，截断k位后为$x’$，则有$B2T(x’) = U2T(B2U(x’)) = U2T(B2U(x)\;mod\;2^k)$
2.3. 小结
- 注意C语言中有符号数和无符号数的隐式转换
- 注意无符号数的减法溢出
3. 整数计算
3.1. 无符号数
- 无符号数加法
- 正常: $x+y<2^w$，$x + y$
- 溢出: $2^w\le x+y<2^{w+1}$, $x + y - 2^w$
- C语言判断是否溢出：当且仅当求和结果小于任何一个操作数
- 无符号数求反
- 对$0\le x < 2^w$，其w位的无符号逆元$-^u_{w}x$为
- $x = 0, -x = 0$
- $x > 0, -x = 2^w - x$
3.2. 补码
对$-2^{w-1}\le x, y \le 2^{w-1} - 1$，求和结果的范围为$-2^w \le x, y \le 2^w - 2$
- 补码加法
- 由于和无符号位级表示相同，核心可以考虑先转换为无符号加法，即先考虑位级运算，然后将求和结果进行有符号转换，无符号到有符号变化本质就是$mod\;2^w$，对负溢出，溢出的最高位符号被抹去，即加上$2^w$；对正溢出，溢出的最高位符号权值被取为相反数，即减去$2^w$
- 正溢出：当$2^{w-1}\le x + y$，结果为$x + y - 2^w$
- 无溢出：当$-2^{w-1}\le x + y < 2^{w-1}$，结果为$x + y$
- 负溢出：当$x + y < 2^{w-1}$，结果为$x + y + 2^w$
- C语言判断是否溢出：当且仅当$x>0, y>0, x + y <0$或$x<0, y<0, x+y<0$时发生了溢出。
- 补码求反
- 本质上从位级考虑相反数相加都是和为$2^w$
- 当$x = TMin_w$，$-x = TMin_w$
- 当$x > TMin_w$，$-x = -x$
3.3. 乘法
- 无符号乘法
- $x*y = (x\cdot y)\;mod\;2^w$
- 补码乘法
- 无符号和补码乘法具有位级等价性
- $x*y = U2T_2((x\cdot y)\;mod\;2^w)$
- 乘以常数
- 无论是否有符号，由于位级等价性，常数总是能根据位模式转换为一组移位后求和的表达式
- 例如，14表示为1110，则$x * 14$可以表示为
- $(x « 3) + (x « 2) + (x « 1)$
- $(x « 4) - x$
3.4. 除以2的幂
- 注意：整数除法总是舍入到0
- 若结果为正，则向下舍入
- 若结果为负，则向上舍入
- 除以2的幂的无符号除法
- C表达式$x» k$，结果为$\lfloor x/2^k \rfloor$
- 显然由于无符号数非负，因此满足舍入到0
- 除以2的幂的有符号除法
- C表达式$x» k$，结果为$\lfloor x/2^k \rfloor$
- 若x为正数，向下舍入符合整数除法
- 若x为负数，向下舍入不满足整数除法
- 相当于在移位过程中一些正数权被抹除掉了
- 例如：-3/4，使用移位时结果为-1，而除法应为-0.75舍入为0
- 为了解决使用移位表示除以2的幂的问题，需要在移位前通过引入偏置(biasing) 解决这个问题。
- C表达式$(x+(1«k)-1)»k$结果为$\lceil x/2^k \rceil$
- 因此为了对有符号除法使用移位操作，需要对被除数分情况讨论使用对应公式
- C表达式$x» k$，结果为$\lfloor x/2^k \rfloor$