CMU 15-213 Intro to Computer Systems Lecture 2

课程主页: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$单词长度

整型

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

无符号:

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

有符号($x_{w-1}$称为符号位,该方式成为补码表示):

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

不难看出有如下关系

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

  • 1
    2
    3
    4
    5
    #include <limits.h>

    ULONG_MAX
    LONG_MAX
    LONG_MIN

最后看两个例子:

转换

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

显然上述转换是可逆的:

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

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

对于$\text {TMin} \leqslant x \leqslant \text{TMax}$,我们有如下公式

对于$0 \leqslant x \leqslant \text{UMax}$,我们有如下公式

图示如下:

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

C语言中的转换如下:

1
2
3
4
5
6
7
8
9
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}$

证明如下:

原始的值:

现在的值:

来看一个具体例子:

1
2
3
4
short int x = 15213;
int ix = (int) x;
short int y = -15213;
int iy = (int) y;

截断

无符号截断:

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

有符号截断:

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

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

本文标题:CMU 15-213 Intro to Computer Systems Lecture 2

文章作者:Doraemonzzz

发布时间:2020年05月01日 - 11:34:00

最后更新:2020年05月07日 - 22:14:24

原始链接:http://doraemonzzz.com/2020/05/01/CMU 15-213 Intro to Computer Systems Lecture 2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。