课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲的主题是比特，字节和整型数。

用比特表示信息

比特

每个比特是0或1
为什么要用比特？因为电子器件上容易实现
- 易于存储的双稳态元素
- 可靠地通过嘈杂的电线传输

比特可以用来表示二进制数，例如

$15213_{10}=11101101101101_{2}$

字节

一个字节等于8个比特

比特级别的操作

布尔代数

对比特向量同样可以使用上述运算：

上述操作均可以在C语言中使用，分别为$\&, 1, \sim, \wedge$

上述操作可以对任意“整型”数据类型使用
- long, int, short, char, unsigned
将参数视为比特向量
按位操作

注意上述操作要和C语言中的逻辑操作$\& \&, ||,!$加以区分

逻辑操作将$0$视为”False”
将非零视为”True”
总是返回0或1
短路

例子：表示，操作集合

来看一个使用比特向量表示集合的例子：

表示
- 长度为$\mathrm w$的比特向量表示集合$\{0, \ldots, \mathrm w-1\}$的子集
- $a_j=1$如果$j\in A$
  - $01101001 \quad\{0,3,5,6\}$
操作
- & 交集
- | 并集
- ^ 对等差分
- ~ 补集

移位操作

左移：$ {x} << {y} $
- 将比特向量$x$左移$y$个位置，扔掉左边多余的部分
- 在右边填$0$
右移：$ {x} >> {y} $
- 将比特向量$x$右移$y$个位置，扔掉右边多余的部分
- 逻辑移位
  - 左侧填充0
- 算数移位
  - 左侧填充符号位（$x$最左侧的符号）
未定义的行为
- 移位量$<0$或$\ge$单词长度

整型

表示方法：无符号和有符号整型

无符号：

$B 2 U_w(X)=\sum_{i=0}^{w-1} x_{i} \cdot 2^{i}$

$\text{UMin}=0:000 \ldots 0$
$\text{UMax}=2^w-1:111 \ldots 1$

有符号（$x_{w-1}$称为符号位，该方式成为补码表示）：

$B 2 T_w(X)=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}$

$\text{TMin}=-2^{w-1}:100 \ldots 0$
$\text{TMax}=2^{w-1}-1:011 \ldots 1$
其他值：$-1:111 \ldots 1$

不难看出有如下关系

$\begin{aligned} | \text {TMin} |&=\text{TMax}+1\\ | \text {UMax} |&=2\times \text{TMax}+1 \end{aligned}$

在C语言中，可以使用如下方式使用上述特殊值：

```c

include

ULONG_MAX
LONG_MAX
LONG_MIN


最后看两个例子：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050104.jpg?raw=true)

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050105.jpg?raw=true)



##### 转换

有符号整型以及无符号整型和十进制数的转换关系如下：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050106.jpg?raw=true)

显然上述转换是可逆的：

- $\text{U2B}(x)=\text{B2U}^{-1}(x)$
- $\text{T2B}(x)=\text{B2T}^{-1}(x)$

利用复合关系可以得到有符号整型以及无符号整型的转换关系：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050107.jpg?raw=true)

对于$\text {TMin} \leqslant x \leqslant \text{TMax}$，我们有如下公式
$$
T 2 U_w(x)=\left\{\begin{array}{ll}
x+2^{w}, & x<0 \\
x, & x \geqslant 0
\end{array}\right.
$$
对于$0 \leqslant x \leqslant \text{UMax}$，我们有如下公式
$$
U 2 T_{w}(u)=\left\{\begin{array}{ll}
u, & u \leqslant \text{TMax} \\
u-2^{w}, & u>\text{TMax}
\end{array}\right.
$$
图示如下：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050108.jpg?raw=true)

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050109.jpg?raw=true)

映射关系用图片更容易理解：

![](https://github.com/Doraemonzzz/md-photo/blob/master/CMU%2015-213%20Intro%20to%20Computer%20Systems/Lecture2/2020050110.jpg?raw=true)

C语言中的转换如下：

```c
int tx, ty;
unsigned ux, uy;
//显示转换
tx = (int) ux;
uy = (unsigned) ty;

//隐式转换
tx = ux;
uy = ty

如果在单个表达式中混合使用无符号整型和有符号整型，则有符号整型隐式转换为无符号整型
包括比较运算符：$<,>,==,<=,>=$

总结

有符号转换为无符号的基本规则

比特向量不变
但是重新解释
可能会有意外的影响：加减$ 2 ^ {w} $
包含有符号和无符号int的表达式：int被强制转换为无符号

扩展，截断

扩展

无符号拓展比较简单，直接在前面的比特补$0$即可，有符号拓展比较麻烦，具体如下：

任务：
- 给定$w$比特位的有符号整型$x$
- 将其转换为$w+k$比特位有符号整型，并且值相同
规则：
- 将符号位复制$k$份
- $X^{\prime}=X_{w-1}, \dots, X_{w-1}, X_{w-1}, X_{w-2}, \dots, X_{0}$

证明如下：

原始的值：

$v_1=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}$

现在的值：

$\begin{aligned} v_2 &= -x_{w-1} \cdot 2^{w+k-1}+\sum_{i=w-1}^{w+k-2} x_{w-1} 2^i+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}\\ &=-x_{w-1} \cdot 2^{w+k-1}+ x_{w-1} 2^{w-1}(2^k -1)+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}\\ &=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}\\ &=v_1 \end{aligned}$

来看一个具体例子：

short int x = 15213;
int ix = (int) x;
short int y = -15213;
int iy = (int) y;

截断

无符号截断：

$B 2 U_w(X)=\sum_{i=0}^{w-1} x_{i} \cdot 2^{i}$

假设截断为$k$位，则结果为

$B 2 U_k(X)=\sum_{i=0}^{k-1} x_{i} \cdot 2^{i}$

即

$B 2 U_k(X) = B 2 U_w(X)\bmod 2^k$

有符号截断：

$B 2 T_w(X)=-x_{w-1} \cdot 2^{w-1}+\sum_{i=0}^{w-2} x_{i} \cdot 2^{i}$

假设截断为$k$位，则结果为

$B 2 T_k(X)=-x_{k-1} \cdot 2^{k-1}+\sum_{i=0}^{k-2} x_{i} \cdot 2^{i}$

即

$B 2 T_k(X) = U2T_k(B2U_w (X))$

总结

扩展（例如，short int变成int）
- 无符号：添加零
- 有符号：增加符号位
- 两者均产生预期结果
截断（例如，unsigned变成unsigned short）
- 无符号/有符号：比特被截断
- 结果重新解释
- 无符号：mod操作
- 有符号：类似于mod
- 数字小的时候产生预期的行为