信息的表示和处理 及 CS:APP 15213 datalab

信息的表示和处理

在通用计算机中中，字节作为最为最小 的可寻址的内存单元，而不是访问内存中单独的位。

寻址和字节顺序

big endian (大端法)，数据最高字节部分地址在地址处，和人的感觉逻辑相似

little endian (小端法)，低字节部分在低地址处

布尔代数

1 TRUE

2 FALSE

~ NOT

& AND

| OR

^ EXCLUSIVE-OR（异或）

1 ^ 0 = 1

1 ^ 1 = 0

0 ^ 0 = 0

0 ^ 1 = 1

IEEE 754 浮点数

$ V = (-1)^s \times M \times 2^E$

符号(sign) s(1)为负数, s(0)为非负数

尾数(significand) M 是一个二进制小数, 范围为 $1 \sim 2 - \varepsilon $ 或者 \(0 \sim 1 - \varepsilon\)

阶码(exponent) E的作用是对浮点数加权, 权重的范围为2的 E 次方幂

将浮点数的位划分位三个字段，分别对这些值赋值：

一个单独的符号位 s 直接编码符号位 s, 1-bit

k 位的阶码字段 \(exp = e_{k-1} \cdots e_1 e_0\) 编码阶码 E, k=7(单精度), k=11(双精度)

n 位小数字段 \(frac = f_{n-1} \cdots f_1 f_0\) 编码尾数 M, 且编码的值依赖阶码字段的值是否等于 0, n=23(单精度), n=52(双精度)

浮点数的值：

e 为无符号整数，其位表示 \(e_{k-1} \cdots e_1 e_0\)

小数字段 frac 被解释为描述小数值 \(f\), 其中 \(0 \le f \le 1\), 其二进制表示\(0.f_{n-1} \cdots f_1 f_0\)

Bias 是一个等于 $2^{k-1} -1 $ 的偏置值

规格化\((exp !=0, exp != 2^{k}-1)\), 最常遇到的值

阶码的值 \(E = exp - Bias\)

尾数定义 \(M = 1 + f\)

非规格化\((exp == 0)\), 提供表示数值 0 及逐渐接近 0 的方法

阶码的值 $E = 1 - Bias $

尾数定义 \(M = f\)

非规格化\((exp == 2^{k}-1)\), 特殊值 NaN

舍入
表示方法限制了浮点数的范围和精度
偶数舍入(round-to-even) 为默认的舍入方式, 其将数字向上或向下舍入，使得结果的最低有效数字(保留位)是偶数(0)
只有是在两个可能的结果的中间值才考虑向偶数舍入, 大于 0.5 是直接进位的
向上舍入的情况，向下舍入可以不管（反正要丢弃了，不影响结果）
尾数 \(1.BBGRXXX\), 保留位(Guard bit)、近似位(Round bit) 和 粘滞位(Sticky bit)

Round = 1, Sticky = 1 > 0.5 进位

Guard = 1, Round = 1, Sticky = 0 -> 偶数向上舍入

实验部分

1. 只用 ~ 和 & 操作符求两个数的或
摩根定律： $ \neg(p \lor q) = \neg p \land \neg q $
异或：$ p \oplus q = (\neg p \land q) \lor (p \land \neg q)$
所以展开即可

/* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */ int bitXor(int x, int y) { return ~(~(~x & y) & ~(x & ~y)); }

2. 最小的整形补码, 可用符号 ! ~ & ^ | + << >>
$ -2^{31} $ (0xF0000000)

/* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */ int tmin(void) { return 1 << 31; }

3. 判断是否是最大的整形数，可用符号 ! ~ & ^ | +*
直接利用 INT_MAX + INT_MAX + 2 = 0 的结果并且排除0xFFFFFFFF，还要注意一个不能直接相加，只能 x+1+x+1

/* * isTmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * Legal ops: ! ~ & ^ | + * Max ops: 10 * Rating: 2 */ int isTmax(int x) { return !(x + 1 + x + 1) & !!(x + 1); }

4. 判断所有的奇数位为1，可用符号 ! ~ & ^ | + << >>
排除偶数位的干扰得到奇数位的值，再与奇数位的 0xaaaaaaaa 做亦或运算，如果正确结果必为 0，这时做 非运算 就可以了
所有先得到 0xaaaaaaa

/* * allOddBits - return 1 if all odd-numbered bits in word set to 1 * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 12 * Rating: 2 */ int allOddBits(int x) { int bits0_15 = (0xAA << 8) + 0xAA; int bits0_23 = (bits0_15 << 8) + 0xAA; int bits0_31 = (bits0_23 << 8) + 0xAA; return !((bits0_31 & x) ^ bits0_31); }

5.取负，可用符号 ! ~ & ^ | + << >>

/* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */ int negate(int x) { return ~x + 1; }

6. 判断是否是 ASCII 数字，可用符号 ! ~ & ^ | + << >>

判断高 6_31 位，必须是 0

判断 4 5 位，必须为 1

判断第四位，通过相加6判断是否有进位

/* * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' * to '9') Example: isAsciiDigit(0x35) = 1. isAsciiDigit(0x3a) = 0. * isAsciiDigit(0x05) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 3 */ int isAsciiDigit(int x) { int bit6_31 = !((x >> 6) & (~0)); int bit_5 = (x & 0x20) >> 5; int bit_4 = (x & 0x10) >> 4; int bits0_3 = !(((x & 0xF) + 6) & 0x10); return bits0_3 & bit_4 & bit_5 & bit6_31; }