CMU 15-213 Intro to Computer Systems Lecture 3

课程主页: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/

这一讲的主题是整型数的其他操作以及指针的内容。

整型

加法

无符号加法

  • 无符号加法的方式为按正常加法运算,然后不考虑溢出位

  • 最终的结果为取模运算

可视化(数学)整数加法

  • 整数加法
    • 输入为$4$比特的整数$u,v$
    • 计算真实结果$\operatorname{Add}_{4}(u, v)$
    • 结果和$u,v$呈线性关系
    • 形成平面
可视化无符号加法

检查无符号加法的溢出

假设$u,v$为无符号整数,$s=u+v$,那么当且仅当$s<u$(或等价的$s<v$)时产生溢出,这是因为

补码加法

  • TAdd和UAdd比特级别行为相同,具体如下

    • 1
      2
      3
      int s, t, u, v;
      s = (int) ((unsigned) u + (unsigned) v);
      t = u + v
    • 最后的结果是s==t

计算公式如下

TAdd溢出
  • 真实的加法需要$w+1$比特
  • 处理方法为不考虑最高位
  • 将其余的比特视为补码

可视化补码加法

对补码加法进行可视化

    • 4比特的补码
    • 范围从$-8$到$7$
  • 截断方法
    • 如果和$\ge 2^{w-1}$
      • 变成负数
    • 如果和$<-2^{w-1}$
      • 变成正数

公式如下

如果画图表示则为:

检查补码加法的溢出

利用上述公式可得如下结论:对于满足$\operatorname{TMin}_{w} \leqslant x, y \leqslant \text{TMax}_{w}$的$x,y$,记$s=x+y$。如果$x>0,y>0$且$s<0$,则发生了正溢出;如果$x<0,y<0$且$s\ge0$,发生了负溢出。

求反

方法1
  • 假设输入为$x$,我们希望得到$-x$
  • 方式为对比特向量取反然后加$1$

证明如下:

取反

加$1$得到

不难看出我们有

方法2

还有另一种求$-x$的方式,假设

令$k$是$x$最右边的$1$的位置,即

那么

证明:

首先

其次

乘法

  • 目标:计算$ w $位数字$ x,y $的乘积

    • 对于有符号或者无符号整型
  • 但是,确切的结果可能大于$ w $位

    • 无符号:最多$ 2 w $位

      • 结果范围:
    • 二进制补码最小值(负数):最多$ 2 w-1 $

      • 结果范围:
    • 二进制补码最大值(正):最多$ 2 w $位,为$\left(\text{TMin}_{w}\right)^{2}$

      • 结果范围:
  • 所以,如果要保持准确结果

    • 计算每种乘法时都需要增加比特位
    • 在软件中完成(如果需要)
C中无符号乘法

  • 标准乘法

    • 忽略高于$w$比特的部分
  • 最终的结果为取模运算

C中有符号乘法

  • 标准乘法
    • 忽略高于$w$比特的部分
    • 有符号和无符号部分有些不同
    • 低位部分相同

计算公式为

其中$u.v$表示数学乘法。

使用移位操作代替乘以2的幂
  • 操作

    • $u<<k$给出$u\times 2^k$(有符号乘法和无符号乘法均成立)
  • 例子

    • 1
      u << 3 == u * 8
    • 1
      (u << 5) – (u << 3) == u * 24
    • 大多数机器中左移比乘法快

      • 编译器会自动生成这样的代码

方法的证明:

假设$x$的$w$位二进制表示为$\left[
x_{w-1} , x_{w-2} \cdots x_{0}
\right]$,那么$\left[x_{w-1}, x_{w-2}, \cdots, x_{0}, 0, \cdots, 0\right]$给出了$x2^k$的$w+k$位二进制表示:

对于固定长度的表示,高$k$位被丢弃,左移$k$位的二进制表示为

所以

所以对于无符号整数

对于有符号整数,利用

可以得到相同的结果。

一般情形

现在考虑一般的情形,假设我们需要计算$u\times K$,其中$K$为常数,将$K$表达为一组$0$和$1$交替的序列

考虑一组从位置$n$到位置$m$的连续$1$,那么可以用如下方式计算这部分的对于乘积的影响:

使用移位操作代替除以2的幂(无符号)
  • $u>>k$给出$\left\lfloor\text { u } / 2^{k}\right\rfloor$
  • 使用逻辑移位

证明:

假设$x$的$w$位二进制表示为$\left[
x_{w-1} , x_{w-2} \cdots x_{0}
\right]$,右移$k$位的二进制表示为$\left[
0, \cdots ,0 ,x_{w-1} , x_{w-2} \cdots x_{w-k}
\right]$

所以

使用移位操作代替除以2的幂(有符号)
  • $u>>k$给出$\left\lfloor\text { u } / 2^{k}\right\rfloor$
  • 使用算数移位

当$u>0$时上述方法和无符号情形一致,但是当$u<0$时则会产生有问题的结果,例如取$u=-12340$:

考虑$k=4,8$时的结果,在C语言中实际结果为$-771$和$-48$,之所以和C语言中的结果不同,是因为上述算法朝着离$0$更远的方向舍入,所以当$u<0$时要向上舍入,达到上述效果利用如下事实即可

在此问题下使用如下方式即可,注意这里$y=2^k$

  • $(u+(1<>k$

C代码如下

1
(x<0 ? x+(1<<k)-1 : x) >> k

总结

  • 加法:
    • 无符号/有符号:正常加法,然后截断,在位级别上相同的操作
    • 无符号:加法$\bmod 2^{w}$
      • 数学加法+可能减去$2^{w}$
    • 有符号:修改的加法$\bmod 2^{w}$(在适当范围内)
      • 数学加法和可能减去或加上$2^{w}$
  • 乘法:
    • 无符号/有符号:普通乘法后截断,在位级别上进行相同的操作
    • 无符号:乘法$\bmod 2^{w}$
    • 有符号:修改后的乘法$\bmod 2^{w}$(在适当范围内)
一些例子
例1
1
2
3
unsigned i;
for (i = cnt-2; i >= 0; i--)
a[i] += a[i+1];

上述代码会死循环,因为无符号整数永远$\ge 0$,$0-1 \rightarrow \text{UMax}$,正确方式如下

1
2
3
unsigned i;
for (i = cnt-2; i < cnt; i--)
a[i] += a[i+1];
例2
1
2
3
4
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DELTA >= 0; i-= DELTA)
. . .

上述代码也会死循环,因为DELTA是无符号整数,赋值时会被强制转换成无符号整数。

正确方式如下:

1
2
3
size_t i;
for (i = cnt-2; i < cnt; i--)
a[i] += a[i+1];
何时使用无符号整数
  • 在执行模块化算术时使用
    • 多精度算术
  • 在使用位表示集时使用
    • 逻辑右移,无符号扩展

内存中的表示形式,指针,字符串

面向字节的内存组织

  • 程序根据地址引用数据
    • 从概念上讲,可以将其设想为非常大的字节数组
      • 实际上不是,但是可以这样想
    • 地址就像是该数组的索引
      • 并且指针变量存储一个地址
    • 注意:系统为每个“进程”提供专用地址空间
    • 将进程视为正在执行的程序
    • 因此,程序可以破坏自己的数据,但不能破坏其他数据

Machine Words

  • 任何给定的计算机都具有“字长”
    • 整型数据(地址)的标称大小
    • 直到最近,大多数机器都使用32位(4字节)作为字长
      • 地址限制为4GB($2^{32}$比特)
    • 越来越多的机器具有64位字长
      • 可能有$18.4\times 10^{18}$个地址
    • 机器仍支持多种数据格式
      • 字长的分数或整数倍
      • 但总是整数比特

来看一个具体例子:

比特顺序

比特顺序分为大端法和小端法,考虑变量$x$,其值为$0\text{x} 01234567$,地址为$0\text{x}100$,大端法和小端法的表示区别为:

表示字符串

  • C中字符串
    • 用字符数组表示
    • 每个字符均以ASClI码表示
      • ASClI码是字符集的标准7位编码
      • 字符“0”的代码为0x30
        • 数字$ i $的代码为0x30+i
    • 字符串应以空值结尾
      • 最终字符= 0
  • 兼容性
    • 比特顺序不是问题

习题

初始化

1
2
3
4
int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;

这里假设int用32字节表示。

1.

错误,反例如下

2.

正确,因为$\mathbf{ux}$是无符号整数。

3.

正确,因为$\mathbf x \& 7$表示$\mathbf x$的最后三位为$1$,所以左移30位后第一位仍然为$1$

4.

错误,$-1$的二进制表示为全$1$,$\mathbf {ux}$将其转换为无符号整数,即$\text{UMax}$。

5.

错误,取$\mathbf y = \text{TMin}$,利用$-\mathbf y=\text{TMin}$

6.

错误,取较大$\mathbf x$就会产生错误。

7.

错误,正溢出。

8.

正确,因为每个正数对对应一个负数。

9.

错误,取$\mathbf x =\text{TMin}$

10.

错误,例如取$\mathbf x =0$,那么得到的结果为$0$。注意取非零$\mathbf x$,上述结论均成立,因为$\mathbf x |-\mathbf x$第一位一定是$1$,右移$31$位后会得到全部为$1$的二进制数,即$-1$

11.

正确。

12.

不正确,例如$x$取负数的时候。

13.

错误,取$\mathbf x = \text{TMin}=[1,0,\ldots, 0]$,那么$\mathbf x -1= [0,1,\ldots, 1]$,所以

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

文章作者:Doraemonzzz

发布时间:2020年05月07日 - 21:36:00

最后更新:2020年05月12日 - 12:58:56

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

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