数据表示

• 位操作
  • 基本运算
    • 与、或、非、异或、左移。
    • 逻辑右移：在高位补 $0$。
    • 算术右移：在高位补充之前的最高位数字。
    • 移位量大于等于字长或小于 $0$ 在 C 语言中是未定义行为。
  • 优先级
    • 位运算符优先级：
      • 按位非 ~
      • 左移/右移 << >>
      • 按位与 &
      • 按位异或 ^
      • 按位或 |
    • 结合算术运算时，算术运算符优先级高于移位运算符。
• 内存布局
  • 字长
    • 字长等于 CPU 的位数。
    • 地址按照字长的倍数对齐。
  • 字节顺序
    • 字节顺序指定多字节数据类型中每个字节的顺序。
    • 大端序：高位在前，低位在后。Internet 使用。
    • 小端序：高位在后，低位在前。x86、ARM 使用。
• 整数
  • 编码
    • 二进制位向量：底层储存方式，无编码，以下用 $B$ 表示，记作 $[x_{w - 1}, \dots, x_0]$。
    • 无符号整数：把二进制位向量直接解释为整数，以下用 $U$ 表示。
    • 有符号补码整数：最高位作为符号位，剩下的位储存数或其按位取反加 $1$，以下用 $T$ 表示。
    • C 语言标准不强制有符号整数使用补码，但是几乎都是使用补码。
  • 编码解释
    • 对于同一个位向量，使用不同的编码，可以有不同的解释的值。
    • 无符号 $B2U_w(\boldsymbol x) = \displaystyle \sum_{i = 0}^w x_i 2^i$。
    • 有符号 $B2T_w(\boldsymbol x) = \displaystyle -x_{w - 1} 2^{w - 1} + \sum_{i = 0}^{w - 1} x_i 2^i$
    • 逆运算用 $U2B(x)$、$T2B(x)$ 表示。
    • 无符号最值 $UMin = 0$，$UMax = 2^{w} - 1$。
    • 补码最值 $TMin = -2^{w - 1}$，$TMax = 2^{w - 1} - 1$。
  • 同大小强制转换
    • 基本原则：在补码和无符号之间转换，底层的位向量不会变，只是改变编码方式。
    • 补码转无符号 $T2U(x) = B2U(T2B(x)) = x + x_{w - 1} 2^w = \begin{cases} x, & x \ge 0 \\ x + 2^w, & x < 0 \end{cases}$。
      • 非负数和负数转换后，区间顺序颠倒，负数变成大正数。
      • 非负数值不变，$-1$ 转换为 $UMax$，$TMin$ 转换为 $TMax + 1$。
    • 无符号转补码 $U2T(u) = B2T(U2B(u)) = \begin{cases} u, & u < 2^{w - 1} \\ -2^w + u, & u \ge 2^{w - 1} \end{cases}$。
    • 在同一个运算符两侧，如果同时存在无符号和补码，则会转换补码为无符号，再进行比较。
  • 扩展
    • 基本原则：扩展前后，整数的值都不变。
    • 无符号 $U_w2U_{w + k}(u) = B2U_{w + k}([\underbrace{0, \dots, 0}_{k}, U_w2B(u)]) = u$
      • 直接在最高位前补 $0$。
    • 补码 $T_w2T_{w + k}(x) = B2T_{w + k}([\underbrace{x_{w - 1}, \dots, x_{w - 1}}_{k}, U_w2B(x) ]) = x$
      • 在最高位前复制最高位，保证符号不变，这种机制叫符号扩展。
  • 截断
    • 基本原则：截断都在位级别保留最低的若干位，再重新解释为值。
    • 无符号 $U_{w + k}2U_w(u) = B2U_w([u_{w - 1}, \dots, u_0]) = u \bmod 2^w$。
    • 补码 $T_{w + k}2T_w(x) = B2T_w([x_{w - 1}, \dots, x_0])$。
  • 加法
    • 基本原则：无符号和补码的加法在位级别上一样，均截断理论结果的位向量。
    • 无符号 $UAdd_w(u, v) = (u + v) \bmod 2^w$。
    • 补码 $TAdd_w(x, y) = U2T((T2U(x) + T2U(y)) \bmod 2^w)$。
  • 乘法
    • 基本原则：无符号和补码的乘法法在位级别上一样，均截断理论结果的位向量。
    • 无符号 $UMult_w(u, v) = (uv) \bmod 2^w$。
    • 补码 $TMult_w(x, y) = U2T((T2U(x) T2U(y)) \bmod 2^w)$。
    • 如果两个 $w$ 位整数相乘，则精确表示结果需要 $2w$ 位。
  • 移位实现的乘除法
    • $x$ << $k = x 2^k$
    • $x$ >> $k = \left\lfloor \dfrac{x}{2^k} \right\rfloor$
    • 对于有符号数，实现向 $0$ 取整除法：$(x + (2^k - 1))$ >> $k$。
• 浮点数
  • 编码
    • IEEE 754 浮点数的二进制表示分为三部分：符号位 $s$、阶码 $Exp$、尾数 $Frac$。
      • 分别对应 $(-1)^s M 2^E$ 的符号位 $s$、指数 $E$、尾数 $M$，但彼此不直接相等。
    • 精度：
      • 单精度：32 位，阶码用 8 位，尾数用 23 位。
      • 双精度：64 位，阶码用 11 位，尾数用 52 位。
    • Normalized Value：
      • $Exp$ 为全 $0$ 和 全 $1$ 时，浮点数是 Normalized Value。
      • 阶码用偏置编码指数，$E = Exp - \Delta$，其中 $\Delta = 2^{k - 1} - 1$，$k$ 为阶码长度。
      • 尾数表示为 $M = 1.[Frac]$，$[Frac]$ 直接使用尾数部分的二进制串。
    • Denormalized Value：
      • $Exp$ 全为 $0$ 时，浮点数是 Denormalized Value。
      • 指数规定为 $E = 1 - \Delta$。
      • 尾数表示为 $M = 0.[Frac]$。
    • 无穷大：$Exp$ 全为 $1$，$Frac$ 为全 $0$。
    • NaN：$Exp$ 全为 $1$，$Frac$ 不为全 $0$。
  • 舍入
    • 四种舍入方式：
      • 向下舍入
      • 向上舍入
      • 向零舍入
      • 向偶数舍入：类似四舍五入，除了当被舍入的最高位为一半时，向被保留的最后一位的偶数方向舍入。
        • $1.2350$ 和 $1.2450$ 都舍入为 $1.24$。
    • 二进制下的向偶数舍入：
      • 仅当出现 $\mathrm{i \cdots i}.\mathrm{f \cdots f}10 \cdots 0$ 时，需要特殊考虑舍入方向
      • 舍入向最后一个 $\mathrm{f}$ 为 $0$ 的方向。
  • 加法
    • 设浮点数 $x = (-1)^{s_x} M_x 2^{E_x}, y = (-1)^{s_y} M_y 2^{E_y}$，且 $E_x > E_y$，则加法按照以下步骤：
      • 把 $M_y$ 与 $M_x$ 对齐，即 $M_y 2^{E_y} \to \dfrac{M_y}{2^{E_x - E_y}} 2^{E_x} = M_y' 2^{E_x}$，结果的阶码则为 $E = E_x$。
      • 相加 $(-1)^{s_x} M_x$ 与 $(-1)^{s_y} M_y'$，得到 $M$。
      • 根据 $M$ 修正结果：
        • 如果 $M \ge 2$，则 $M$ 右移除以 $2$，递增 $E$。
        • 如果 $M < 1$，则 $M$ 左移 $k$ 位，$E$ 减去 $k$，要求最后结果满足尾数的定点数格式。
      • 如果 $E$ 超出范围，则其饱和溢出，即最终结果表示为无穷大。
      • 舍入 $M$ 到合适的精度。
    • 代数性质：
      • 不满足结合律。
      • 基本可逆，除了无穷大和 NaN。
      • 基本满足单调性 $a \ge b \implies a + c \ge b + c$，除了无穷大和 NaN。
  • 乘法
    • 设浮点数 $x = (-1)^{s_x} M_x 2^{E_x}, y = (-1)^{s_y} M_y 2^{E_y}$，则乘法按照以下步骤：
      • 计算符号位 $s = (s_x + s_y) \bmod 2 = s_x \oplus s_y$。
      • 计算指数 $E = E_x + E_y$。
      • 计算尾数 $M = M_x M_y$。
      • 根据 $M$ 修正结果、处理溢出和舍入，方法同加法。
    • 代数性质：
      • 不满足结合律。
      • 对加法不满足分配律。
      • 基本满足单调性 $a \ge b \implies a c \ge b c\ (c \ge 0)$，除了无穷大和 NaN。