目录
第二章 信息的存储和表示
信息存储
十六进制表示法
(略)
字数据大小
- 大多数计算机使用8bit的块(字节)作为最小的可寻址的内存单元
- 字长指明了指针数据的标称大小(?)
- 64位系统和32位系统向后兼容
- C语言中有些数据类型的具体大小依赖于程序的编译,C99引入
int32_t
和int64_t
类型,指明数据的长度 - C标准对不同数据类型的数字的范围设置了下界,没有设置上界
寻址和字节顺序
- 存储规则:对象的地址是什么?在内存中如何排列这些字节?
- 地址:多字节对象的存储地址为连续字节序列的最小字节地址
- 排列方式:
- 小端法:低字节存在低地址
- 大端法:低字节存在高地址
- 默认规则:书写时,地址从左往右表示从低到高,字节从左往右表示从高到低
- 关心字节顺序的场合:
- 网络数据传输
- 阅读字节序列
- 规避正常的类型系统,比如强制类型转换或者联合允许一种数据类型引用一个对象
- 代码示例:按字节读取内容
//按照字节打印数据中的内容
#include<bits/stdc++.h>
using namespace std;
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, int len){
int i;
for(i = 0; i < len; ++i){
printf(" %.2x", start[i]);
}
printf("\n");
}
void show_int(int x){
show_bytes((byte_pointer)&x, sizeof(int));
}
int main(){
int num;
cin >> num;
show_int(num);
return 0;
}
字符串的表示
- 用ASCII码表示
- ASCII码只能表示英文字符,更一般的字符采用Unicode
代码表示
- 二进制代码不兼容,即不同系统上编译得到的二进制代码不同
布尔代数
- 运算:与、或、非
- 位向量
- 位向量表示有限集合
C语言中的位运算
- 将十六进制转换为二进制执行二进制运算,然后将结果转换为十六进制
C语言中的逻辑运算
- 0表示false,非0表示true
- 与位运算的不同:
- 位运算的参数是0或1
- 逻辑运算有短路原则
C语言中的移位运算
\([x_{\omega - 1}, x_{\omega - 2}, ..., x_0]\)
- 左移:高位舍弃,低位补0 $ [x_{\omega - 1 - k}, x_{\omega - 2 - k}, ... x_0, \underbrace{0, \cdots, 0}_{k个}]$
- 右移:
- 算数右移:补符号位 \([\underbrace{x_{\omega - 1}, ..., x_{\omega -1}}_{k个}, x_{\omega -1}, x_{\omega - 2}, ..., x_k]\)
- 逻辑右移:补0 \([\underbrace{0, ..., 0}_{k个}, x_{\omega - 1}, ..., x_k]\)
整数的表示
整型数据类型
- 典型实现中,负数比正数多1个
- C语言标准中规定(1)固定了数据大小(2)正数和负数对称
数据编码
假设整型数据类型有\(\omega\)位,将其表示记作位向量\(\vec x = [x_{\omega - 1}, x_{\omega - 2}, \cdots, x_0]\)
无符号数编码
- 定义:
\[ B2U_{\omega}(\vec x)=\sum_{i=0}^{\omega - 1} x_i 2 ^ i \]
范围:\(Umax = \sum\limits_{i = 0}^{\omega - 1} 2 ^ i = 2 ^\omega -1\)
示例:
- 定理:\(B2U_\omega(\vec x)\)是一个双射
补码表示
定义:
\[ B2T_{\omega}(\vec x) = -x_{\omega - 1}2^{\omega - 1} + \sum_{i = 0}^{\omega - 2}x_i 2 ^i【注】补码表示中,最高位被理解为负权 \]
【注】补码表示中,最高位被理解为负权范围:\(Tmin = -2^{\omega - 1}, Tmax = \sum\limits_{i = 0} ^ {\omega - 2}2 ^ i = 2 ^{\omega - 1} - 1\)
-
示例:
定理:\(B2T_\omega(\vec x)\)是一个双射
【注】
- 补码的范围中:\(\vert Tmin\vert = \vert Tmax\vert + 1\)
补码和无符号数:\(Umax = 2Tmax + 1\)
所有机器都将有符号数表示为补码,尽管C语言标准没有明确规定
反码表示
- 定义:
\[ B2O_{\omega}(\vec x) = -x_{\omega - 1}(2^{\omega - 1} - 1) + \sum_{i = 0}^{\omega - 2}x_i2^i \]
原码表示
- 定义:
\[ B2S_\omega(\vec x) = (-1)^{x_{\omega - 1}}\times \sum_{i = 0}^{\omega - 2}x_i2^i \]
有符号数和无符号数之间的转换
- C语言强制类型转换:不改变位级表示,只改变位的解释方式
补码转无符号数
补码转为无符号数:
\[ T2U_\omega(x) = \begin{cases} x + 2 ^\omega & x < 0,\x & x \geq 0 \end{cases} \]推导:
\[ \begin{align} B2U_\omega (\vec x) - B2T_\omega(\vec x) &= x_{\omega - 1}2^\omega \Longrightarrow B2U_\omega(\vec x) = x_{\omega - 1}2^\omega + B2T_\omega(\vec x)\T2U_\omega(x) &= B2U_\omega(T2B_\omega(x)) \&= x_{\omega -1}2^\omega + B2T_{\omega}(T2B_\omega)(x)\&= x_{\omega- 1}2^\omega + x \end{align} \]
- 理解:将补码中最高位解释为负权变为解释为正权,将补码看做无符号数时,正数不变,负数变为一个更大的数
- 示例:
无符号数转补码
- 转换:
\[ U2T_{\omega}(x) = \begin{cases} u & u \leq Tmax_\omega \u - 2 ^ \omega & u > Tmax_\omega \end{cases} \]
- 推导(同补码转无符号数)
总结
C语言中的有符号数和无符号数的转换
- C语言中默认数字都是有符号
- 声明一个无符号常量需要在数字后面缀上‘U’
- 一个运算中同时出现有符号数和无符号数时,会被隐式转换为无符号数
扩展数字的位表示
无符号数的0扩展
- \(u_\omega = [u_{\omega -1}, \cdots, u_0]\longrightarrow u'_{\omega + k} = [\underbrace{0, \cdots, 0}_{k个}, u_{\omega -1}, \cdots, u_0]\)
补码的符号扩展
- 定义
\[ x_\omega = [x_{\omega - 1}, \cdots, x_0]\longrightarrow x'_{\omega + k} = [\underbrace{x_{\omega-1}, \cdots, x_{\omega - 1}}_{k个}, x_{\omega - 1}, \cdots, x_0] \]
- 推导
\[ \begin{align} B2T_{\omega + 1}(\vec x') &= -x_{\omega -1}2^\omega + \sum_{i = 0}^{\omega - 1}x_i2^i\&= -x_{\omega - 1}2^\omega + x_{\omega -1}2^{\omega - 1} + \sum_{i=0}^{\omega - 2}x_i 2^i\&= -x_{\omega - 1}2^{\omega -1}+\sum_{i=0}^{\omega - 2}x_i 2^i\&= B2T_\omega(\vec x) \end{align} \]
截断数字的位表示
无符号数的截断
- 定理
\[ \vec x = [x_{\omega -1 }, \cdots, x_0], \vec x' = [x_{k-1}, \cdots, x_0]\x' = x \mod 2^k \]
- 推导:截断的部分对应的位权为\(2^{k}, \cdots, 2^\omega\)
补码的截断
- 定理
\[ \vec x = [x_{\omega -1 }, \cdots, x_0], \vec x' = [x_{k-1}, \cdots, x_0]\x' = U2T_k(x\mod 2^k) \]
- 推导:以无符号数为中介
整数的运算
无符号数加法
- 定义运算\(+_\omega^u\),将无符号数\(x, y\)相加后截断\(\omega\)位,可以视作是一种模运算
- 无符号数加法:
对于满足\(0\leq x, y < 2^\omega\),有:
\[
x+_\omega^u y = \begin{cases}
x + y & x + y < 2 ^ \omega \x + y - 2 ^ \omega & x + y \geq 2 ^\omega
\end{cases}
\]
- 溢出判断:对于\(s = x+_\omega^uy\),当且仅当\(s < x\quad or\quad s < y\)时发生溢出
- 无符号数求反:模数加法形成了一个阿贝尔群,定义\(x\)的反为:
\[ -_\omega^u x = \begin{cases} x & x = 0\2^\omega - x & x > 0 \end{cases} \]
补码加法
- 定义运算\(+_\omega^t\),将有符号数\(x, y\)相加后截断\(\omega\)位,可以视作是一种模运算
- 补码加法:
\[ x+_\omega^t y=\begin{cases} x+y-2^\omega & 2 ^{\omega - 1} \leq x + y\x+y & -2^{\omega -1 } \leq x + y < 2 ^{\omega -1}\x+y+2^\omega &x + y < -2^{\omega -1} \end{cases} \]
【注】还是来源于截断,当没有溢出时,不发生截断;溢出的情况只会是“正+正”或者“负+负”;“正+正”溢出时,符号位为0,数字部分的最高位变为1(进位导致增加的数字),截断后原有的符号位会被丢弃,符号位变为1,真实的值为\(x+y=2^{\omega -1} + \sum\limits_{i=0}^{\omega -2}x_i2^i\),截断后的值为\(x+_\omega^t y- = 2^{\omega -1} + \sum\limits_{i=0}^{\omega -2}x_i2^i\),因此\(x+_\omega^t y = x + y - 2^\omega\);负溢出解释相似。
- 推导:
有符号和无符号具有相同的位级表示,因此先将参数转换为无符号数,然后按照无符号数运算,最后将结果转换为补码
\[
\begin{align}
x+_\omega^u y &= U2T_\omega(T2U_\omega(x) + T2U_\omega(y))\&= U2T_\omega((x_{\omega-1}2^\omega + y_{\omega - 1}2^\omega+x+y)\mod 2^\omega)\&= U2T_\omega((x+y)\mod 2^\omega)
\end{align}
\]
记\(z=x+y, z' = z\mod 2^\omega, z'' = U2T_\omega(z')\)
若\(-2^{\omega}\leq z < -2^{\omega-1}\),则\(z'=z+2^\omega\),因此\(0\leq z' < 2^{\omega -1}\),故\(z''=z'\)
其余三种情况以此类推
- 补码加法溢出判断:“正+正=负”或者“负+负=正”
补码的非
- 定义:对于满足\(Tmin\leq x \leq Tmax\)的\(x\)
\[ -_\omega^tx=\begin{cases} Tmin &x = Tmin\-x & x>Tmin \end{cases} \]
- 根据位级表示计算补码的非:
- 各位取反再加1:-5=[1011], [0100] + [0001] = [0101] = 5
- 将符号位(包含符号位)与最后一个1之间的位取反:5=[0101], [1011] = -5
无符号乘法
- 定义:\(x*_\omega^uy=(xy)\mod 2^\omega\)
补码乘法
- 定义:\(x*_\omega^t y=U2T_\omega({(xy)\mod 2^\omega})\)
- 无符号和补码乘法的位级等价性
给定长度为\(\omega\)的位向量\(\vec x, \vec y\),用补码形式定义的整数为\(x, y\),用无符号定义的整数为\(x', y'\),则:
\[
T2B_\omega(x*_\omega^t y) = U2B_\omega(x'*_\omega^u y')
\]
证明
\[
\begin{align}
(x'*y')\mod 2^\omega &= ((x_{\omega -1}2^\omega+x) \cdot (y_{\omega -1}2^\omega + y))\mod 2^\omega\&= (xy)\mod 2^\omega\T2U_\omega(x*_\omega^t y)&=T2U_\omega(U2T_\omega((x\cdot y)\mod 2^\omega))\&= x\cdot y \mod 2^\omega\T2B_\omega(x*_\omega^t y)&=U2B_\omega(T2U_\omega(x*_\omega^t y))\&=U2B_\omega((x\cdot y)\mod 2^\omega)
\end{align}
\]
乘常数
- 乘2的幂:\(x\cdot 2^k = x << k\)
- 乘以常数K:将常数K分解为{0,1}序列,然后通过移位和加法
- 计算\(x\cdot K\)
- 分解K:\(K = [(0...0)(1...1)(0...0)...(1...1)]\)
- 计算:考虑从\(n\)位到\(m\)位(\(n \geq m\))为连续的1,有两种计算方案:
- \((x<<n) + (x <<(n-1))+...+(x<<m)\)
- \((x<<(n+1)) - (x<<m)\)
除以2的幂
对于无符号数,\(x>>k\)产生数值\(\lfloor x/2^k\rfloor\)
-
对于有符号数
\(x>0\)时同无符号数
\(x<0\)时,\(x>>k\)产生数值\(\lfloor x/2^k\rfloor\),\((x+(1<<k) - 1)>>k\)产生数值\(\lceil x/2^k\rceil\)
-
偏置的设计:
注意到$\lceil x/y\rceil = \lfloor (x+y-1)/y\rfloor \(,设\)x = qy+r\(,因此\)\lfloor (x+y-1)/y\rfloor=q+\lfloor(r+y-1)/y\rfloor\(,当\)r\(为0时,后面一项为0,当\)r>0\(时后面为1。取\)y=2^k$,即可得到带偏置的除法公式