信息的表达和处理

大小端

多字节类型的表达方式

大端法：低地址存放高位
小端法：低地址存放低位

#include <stdio.h>

void out(unsigned char* p, size_t size)
{
    for (size_t i = 0; i < size; i++)
    {
        printf("%.2x ", p[i]);
    }
}
int main()
{
    int p = 0x01234567;
    out((unsigned char *)&p, sizeof(int));
    return 0;
}

大小端判断也常常作为面试题出现，如上，十六进制数 0x01234567

每两个个十六进制数占8个bit，因此，使用一个char获得起始地址所存放的两个十六进制数即可判断该机器是大端还是小端

1
2
3

int x = 0x01234567;
unsigned char * p = (unsigned char *)&x;
return p == 0x67;

大小端最常见的应用就是使用TCP传输数据时的字节序转换，例如传输一个 =int= 之类的跨字节类型的数据，就需要进行大小端的转换

移位运算

逻辑右移：高位补0
算术右移：高位补符号位

几乎所有的编译器都对

无符号数，进行逻辑右移
有符号数，进行算术右移

整数

无符号数

假定

符号 $B2U_w$ 为w位二进制数转无符号数

符号 $B2T_w$ 为w位二进制数转补码

编码规则

$B2U_w(\vec{x}) \dot= \sum_{i=0}^{w-1}x_i2^i$

原理：无符号数编码的唯一性
- 由公式可知，对于每一个编码都有唯一的无符号数与之对应，反过来亦如此，不存在原码，反码中正负0的情况

有符号数

补码

$B2T_w(\vec{x})\dot=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i$

原理：补码编码的唯一性
- 最高位为负权，因此也不存在正负0
反码：最高位的权为 $2^{w-1}-1$,而$2^{w-1}-1=\sum_{i=0}^{w-2}2^i$, 所以会有
- +0 ：所有位都是0
- -0：所有位都是1
原码：最高位为符号位

转换

假设共有w个位

无符号数的最大值为$2^{w}$ , 最小值为0
补码的最大值为$2^{w-1}$ , 最小值为$-2^{w-1}$

补码转无符号数

$T2U_w(x) = \begin{cases} x + 2^w ,\quad x \lt 0 \\ x, \quad x \ge 0 \end{cases}$

推导

$\begin{align*} B2U_w(\vec{x}) &\dot= \sum_{i=0}^{w-1}x_i2^i = x_{w-1}2^{w-1} + \sum_{i = 0}^{w-2}x_i2^i\\ B2T_w(\vec{x})&\dot=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i\\ B2U_w(x) - B2T_w(x)&= x_{w-1}2^{w}\\ U_w(x) &= T_w(x) + x_{w-1}2^{w}\\ T2U_w(x) &= x + x_{w-1}2^{w}\\ B2U_w(T2B_w(x)) &= T2U_w(x) = x +x_{w-1}2^w \end{align*}$

无符号数转补码

$U2T_w(u) = \begin{cases} u, \quad u \le TMax_w\\ u - 2^w,\quad u >TMax_w \end{cases}$

拓展

无符号数的0拓展

补码的符号拓展，证明，假设符号拓展1位, $B2T_{w+1}(\vec{x})\dot=-x_{w-1}2^{w}+\sum_{i=0}^{w-1}x_i2^i$

$\begin{align*} -x_{w-1}2^{w}+\sum_{i=0}^{w-1}x_i2^i &= -x_{w-1}2^{w}+x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i \\ &= -x_{w-1}(2^w-2^{w-1})+\sum_{i=0}^{w-2}x_i2^i \\ &=-x_{w-1}2^{w-1}+\sum_{i=0}^{w-2}x_i2^i \end{align*}$

可得符号拓展后补码的运算结果与非拓展之前相同

因为最高位为负权，总有

$\begin{align*} 2^w &= 2^{w-1} + 2^{w-1} \\ -2^w+2^{w-1} +...+2^0 &= -2^{w-1}+...+2^0 \\ \end{align*}$

截断

将w位的无符号数，截断为k位，相当于取模操作，证明如下，假设 $w-1=k+n$

$\begin{align*} w-1&=k+n\\ x_{w-1}2^{w-1} \bmod 2^k &= x_{w-1}2^{n}*2^{k} \bmod 2^k \\ &=x_{w-1}2^{n} * 0\\ &=0\\ B2U_w([x_{w-1},x_{w-2},...,x_0]) \bmod 2^k &= \sum_{i=0}^{w-1}x_i2^i \bmod 2^k\\ &=\sum_{i=0}^{k-1}x_i2^i + n *0\\ &=B2U_k \end{align*}$

整数运算

由于类型的字长限制，面对字节膨胀，就会发生溢出，如两个w位的最大值相加，则需要w+1位来表示，但是由于字长限制，我们对w+1位的结果进行截断，得到的数并不是真实的和，这种情况称为溢出

无符号整数加法

定义运算$+_{w}^{u}$ 为无符号整数加法，则有

$x +_{w}^{u}y = \begin{cases} x+y,\quad x+y \lt 2^w\\ x+y-2^w, \quad 2^w \le x+y \le 2^{w+1} \quad overflow \end{cases}$

无符号数取反

$-_{w}^{u}x = \begin{cases} x,\quad x = 0\\ 2^w-x, \quad x > 0 \end{cases}$

则当进行无符号减法运算时，如下

$w = 2 \\ 1-2 = 1 + 2^2 - 2 = 3$

补码加法

定义运算$+_{w}^{t}$为补码加法，则有

$x +_{w}^{t} y = \begin{cases} x + y - 2^w, \quad 2^{w-1} \le x + y\\ x + y, \quad -2^{w-1} \le x + y \lt 2^{w-1} \\ x+y+2^w, \quad x +y < -2^{w-1} \end{cases}$

推导

$\begin{align*} x +_{w}^{t} &= U2T_w(T2U_w(x) +_{w}^{u}T2U_w(y))\\ &=U2T_w[(x_{w-1}2^w +x + y_{w-1}2^w + y)mod2^w]\\ &=U2T_w[(x+y) mod 2^w] \end{align*}$

情况1，负溢出，结果为正数

$\begin{align*} -2^w \le x + y &\lt -2^{w-1} \\ 0 \le (x + y) mod 2^w &\lt -2^{w-1} mod 2^w = 2^w -2^{w-1} = 2^{w-1}\\ U2T_w(x+y) = (x+y)mod 2^w &= x + y + 2^w \ge 0 \\ \end{align*}$

情况2，负正常，结果正常
情况3，正正常，结果正常
情况4，正溢出，结果为负数

$2^{w-1}\le x+y < 2^w \\ x + y < 2^w,\quad if \quad x + y = 2^{w-1}, (x+y)mod 2^w = 2^{w-1} < 2^w\\ so\quad 2^{w-1}\le(x+y)mod2^w < 2^w\\ U2T[(x+y)mod 2^w] = x + y - 2^w$

例题：如何检测补码加法溢出

错误例子

int tadd_ok(int x, int y)
{
  int sum = x + y;
  return (sum - x == y ) && (sum - y == x);
}

假设$x+y$ 发生正溢出

$x+y > 2^{w-1} \\ sum = x+y-2^{w} \\ sum -x = y - 2^{w} < -2^{w-1}\\ so \quad y-2^{w} = y-2^w+2^w = y\\ sum - x \equiv y$

乘法

无符号整数的乘法为

$x*_{w}^{u}y = (x * y) mod 2^w$

补码乘法为

$x*_{w}^{t}y = U2T_w((x * y) mod 2^w)$

这是因为补码乘法和无符号整数乘法具有位级等价性

浮点数

十进制数无法精确表示形如$\frac{1}{3}$这种无法用$x10^y$表示的数，同理，二进制无法精确表示无法写成$x2^y$的数

IEEE浮点数的表示

一共有三个部分

1	[s][exp][frac]

符号s
阶码exp
小数frac

单精度和双精度的不同主要表现为后两者的不同

单精度:exp = 8, frac = 23
双精度:exp = 11, frac = 52

$V=2^E*M$

根据exp值的不同，主要有三种情况

规格化的值

以单精度为例

exp不全为0，也不全为$0\lt exp\lt 255$，此时exp被解释为偏置(biased)

$E=exp-Bias \\ Bias = 2^{w-1}-1\\ Bias = 127 \\ -126(1-127) \le E \le 127(254-127)$

E和M为,k为阶码的位数

$E=e-Bias, Bias=2^{k-1}-1\\ M=1+frac$

非规格化的值

$E=1-Bias\\ M=f$

特殊值(NaN not a number)

$E=2^k \\ M=0\\$

非规格化与规格化的平滑过度

1 2	非规格化0[0000][111], E= 1-7 = -6, M = 1 + 1/2+4/1+8/1 = 7/8, V= 2^{-6} * 7/8 = 7/512 规格化数0[0001][000], E= 0-6 = -6, M = 1 , V = 2^{-6} * 1 = 8/512

看结果可知实现了平滑过度

浮点数在舍入的时候向偶数舍入，而且浮点数运算不具有可结合型

x = a + b + c
y = h + b + c
z = b + c，发生舍入
g = a + z，可能不等于x
d = h + z. 可能不等于y

大小端