CSAPP CH2 信息的表示与操作

作者 QIFAN 日期 2017-02-12
CSAPP CH2 信息的表示与操作

教材官网:http://csapp.cs.cmu.edu/


2.1 Information Storage

位运算

2.2 Integer Representations

w 为位数。掌握这些代号的含义。
$B2T_w$
$B2U_w$
$U2B_w$
$U2T_w$
$T2B_w$
$T2U_w$
$TMin_w$
$TMax_w$
$UMax_w$

一些常用规律:
符号位为 1 的 binary 数字为 b 。$B2U_w(b) - B2T_w(b) = 2^w$
符号位为 0 的 binary 数字为 b 。$B2U_w(b) = B2T_w(b)$
简化一下:$T2U_w(x) = x + x_{w-1}2^w$ 。$x_{w-1}$ 表示 x 以二进制表示的符号位。

C 中 signed 与 unsigned 转换

int tx, tx;
unsigned ux, uy;
tx = (int) ux;
uy = (unsigned) ty;

signed 与 unsigned 比较,signed 自动转为 unsigned 。

extension:
二进制低 bit 到高 bit ,在最高位添加符号位的值。
C 里面转换: short –> unsigned : short –> int –> unsigned

truncating:
二进制高 bit 到低 bit ,不停移除最高位。 $x’ = x \ mod\ 2^k$

2.3 Integer Arithmetic

$x+^u_wy$
判断 overflow 。$x + y \leq x$

abelian group

$x+^t_wy = U2T_w[(x+y)\ mod\ 2^w]$
判断 overflow 。设 s = x + y ,若 s 与 x , y 不同号,则 overflow 。

$TMin_w$ 的相反数是自身。
证明:$TMin_w + TMin_w = -2^{w-1} + -2^{w-1} = -2^w$ 。integer overflow ,所以 $TMin_w +^t_w TMin_w = -2^w + 2^w = 0$ 。

任何乘法 x * K 都可以转换为位运算形式 (x << a) + b

除法:结果为正数向下取整,负数向上取整
unsigned x >> k
two-complement 正数同 unsigned ,负数 (x + (1 << k) - 1) >> k 。也就是先加上 $2^k - 1$ 的 bias ,再右移。

2.4 Floating Point

$10.1001_2 = 1*2^1 + 0*2^0+1*2^{-1}+0*2^{-2}+0*2^{-3}+1*2^{-4}=2.5625_{10}$

IEEE 浮点数表示: $V=(-1)^s * M * 2^E$

标准浮点数格式

bias: bias value = $2^{k-1}-1$ ,k 是 exponent 所占的尾数,在上图中 k = 8 , bias = $2^7-1 = 127$
e:exponent 位置所代表的一个 unsigned value
f:fraction 位置代表的小数

  1. normalized values ,e != 0 && e != 255 ,即不全为 0 且不全为 1 。包括了大多是的浮点数。
    E = e - bias
    M = 1 + f
  2. denormalized values ,e = 0 。表示小于 1 的浮点数。
    E = 1 - bias
    M = f
  3. special values
    无穷 ∞ :exponent 部分全为 1 ,fraction 部分全为 0 。
    非法值 NaN :exponent 全为 1 ,fraction 不为 0 。

不是所有的浮点数都能被二进制表示。假设 n-bit 用于存放小数点,则 $2^{n+1} + 1$ 不能被表示(最大位是 0 ,最小位是 1 ,且二进制长度大于 n + 1 )。

取整。有三种策略:

  1. 向上取整
  2. 向下取整
  3. 四舍五入。假如说保留二进制小数点后三位,1.00101 = 1.001 舍,因为多出来的两位是 01 = 1 < (2^2 - 1) / 2 ,舍。同理 1.00111 = 1.010 入。如果刚好是 0.5 ,看第三位,是 1 就向上取整,是 0 就向下取整。


更新历史:
+ 2017.01.12 第一版