第 2 章 信息的表示和处理
# 第 2 章 信息的表示和处理
向 GCC 指定不同的 C 语言版本
提示
本章中,无特殊说明,
# 2.1 信息储存
# 2.1.1 十六进制表示法
十六进制表示法
记住 `A` 对应 `10`,`C` 对应 `12`,`F` 对应 `15`,可以进行快速转换
# 2.1.2 字数据大小
# 2.1.3 寻址和字节顺序
笔记
size_t
是表示数据结构大小的首选数据类型- 最低有效字节在最前端的方式,称为 小端法
- 最高有效字节在最前端的方式,称为 大端法
- 将内存看做数组,其地址看作索引
# 2.1.4 表示字符串
# 2.1.5 表示代码
# 2.1.6 布尔代数简介
位向量
用位向量表示有限集合
# 2.1.7 C 语言中的位级运算
掩码的使用
# 2.1.8 C 语言中的逻辑运算
# 2.1.9 C 语言中的移位运算
# 2.2 整数表示
引入数学术语来描述计算机编码和操作整数
# 2.2.1 整型数据类型
# 2.2.2 无符号数的编码
借助位向量,来精确的描述二进制编码
# 2.2.3 补码编码
笔记
- 补码 (Two's complement) 与反码 (ones' complement) 英语的含义
- 与负数转换为补码或反码时的操作有关
- 拿正数的原码进行相应的操作
- 与负数转换为补码或反码时的操作有关
# 2.2.4 有符号数与无符号数之间的转换
笔记
- C 语言强制类型转换保持位值不变,只是改变了解释这些位的方式
- 公式 (2.5): 补码转换为无符号数
- 公式 (2.7): 无符号数转换为补码
# 2.2.5 C 语言中的有符号数与无符号数
笔记
- 字面值默认是有符号的,要创建无符号常量,需要加上后缀字符
U
或u
- 有符号数与无符号数之间的转换时,大多数系统遵循底层的位保持不变
- 如果两个运算数一个是有符号的,另一个是无符号的,则 C 语言会隐式的将有符号参数强制类型转换为无符号数参数
# 2.2.6 扩展一个数字的位表示
笔记
- 无符号数的零扩展
- 补码数的符号扩展
提示
- C 语言中
(unsigned) sx
等价于(unsigned)(int) sx
- 先改变大小,再完成有符号数到无符号数的转换
# 2.2.7 截断数字
笔记
- 截断无符号数
- 截断为
位,则
- 截断为
- 截断补码数值
- 先截断,然后再转换为补码
# 2.2.8 关于有符号数与无符号数的限制
提示
- 避免错误的一种方法是绝不使用无符号数
- 但在系统编程中,无符号数还是有其实际应用的
- 如将字仅仅看做是位的集合而没有任何数学意义时
# 2.3 整数运算
# 2.3.1 无符号加法
笔记
- 定义运算
,该操作把整数 截断为 位得到的结果,并将这个结果看做无符号数 - 是模
的加法 - 可以避免数据大小的不断扩张
- 一些编程语言,如 Lisp, 支持无限精度的运算
- 是模
- C 程序执行时,不会将溢出当成错误,但是可以通过程序检测是否发生了溢出
无符号数求反
- 相当于
的加法逆元 - 可以用来解释
# 2.3.2 补码加法
笔记
- 定义
为整数 被截断为 位的结果,并将这个结果看成是补码数 - 存在着正溢出和负溢出
提示
- 补码加法与无符号数加数有着相同的位级表示
检测补码加法中的溢出
- 当且仅当
,但 时,计算发生了正溢出 - 当且仅当
,但 时,计算发生了负溢出
注意
- 在函数的任何测试中,
都应该作为一种测试情况 - 因为
- 因为
# 2.3.3 补码的负数(Two's-Complement Negation)
补码的负数(加数逆元)
提示
- 在 C 语言中
等价于 - 假设
是 位级表示最右边 的位置,则 的位级表示为 - 则
的二进制位级表示为
- 则
# 2.3.4 无符号乘法
无符号数乘法
# 2.3.5 有符号乘法
有符号乘法
- 先截断,再转换为补码
提示
- 对于无符号和补码乘法来说,截断后的乘积的位级表示是相同的
- 其中
与 , 与 的位级表示都是一样的 - 证明从乘法的定义入手
- 其中
检验乘法是否溢出的代码
/* Determine whether the arguments can be multiplied without overflow */
int tmult_ok(int x, int y) {
/* Compute product without overflow */
int64_t pll = (int64_t) x*y;
/* See if casting to int preserves value */
return pll == (int) pll;
}
1
2
3
4
5
6
7
2
3
4
5
6
7
# 2.3.6 乘以常数
笔记
- 整数乘法比移位和加法的代价要大很多,因此许多 C 语言编译器试图以移位、加法和减法的组合来消除很多整数乘以常数情况
- 左移一个数值等价于执行一个与 2 的幂相乘的无符号乘法(或补码乘法)
- 无论是否溢出
提示
- 将常数表示为二进制形式,然后就可以看出移位的选择
- 对于从
到 位连续是 1 的情况,可以用 (x << (n+1)) - (x << m)
来计算
- 对于从
# 2.3.7 除以 2 的幂
提示
C 语言的整数除法总是舍入到 0
- 即当结果为正值时,向下取整;当结果为负值时,向上取整
Python 的整数除法是向下舍入的
>>> 1 // 2 0 >>> -1 // 2 -1
1
2
3
4
除以 2 的幂的无符号除法
- 当
时, C 表达式 产生数值
提示
- 对于补码,移位需要执行算术右移;而且不论正负,其总是向下取整的
- 因为向右移位会舍掉一部分的值,而这些在补码的公式 (2.3) 中都是正值
补码右移的修正
- 当
小于 0 时, 加上 的偏置量 - C 代码计算
(x < 0 ? x + (1 << k) - 1 : x) >> k
- C 语言中算术运算符的优先级大于移位运算符
- 加上偏置的目的是将移位产生的向下舍入变为向上舍入,其利用了如下原理
- 证明可采用 除法算法 中的定理 2
# 2.3.8 关于整数运算的最后思考
提示
- 补码的加法、减法、乘法和除法运算与无符号算术具有相同的位级实现
# 2.4 浮点数
提示
- 浮点表示对形如
的有理数进行编码
# 2.4.1 二进制小数
提示
- 使用位置表示法,只能精确的表示能够被写成
的数 - 其它的数只能近似表示,但增加二进制的长度可以提高精度
- 将一个可以写成
形式的数写成二进制数的过程是 - 使用
的二进制表示,并把二进制小数点插入从右边算起的第 个位置
- 使用
# 2.4.2 IEEE 浮点表示
提示
- 通过给定
和 的值,来表示形如 的数
笔记
# 2.4.3 数字示例
# 2.4.4 舍入
笔记
# 2.4.5 浮点运算
笔记
- 对于浮点值
和 和某个定义在实数上的运算 ,计算将产生 - 相当于对实际运算的精确结果进行舍入后的结果
浮点加法
- 浮点加法是可交换的,但是是不可结合的
- 特例
- 对于任意的
,有
- 浮点加法满足单调性属性
- 即
- 无符号或补码加法不具有这个属性
- 即
浮点乘法
- 具备交换性,不具备结合性
- 在加法上不具备分配律
,浮点乘法满足下列单调性 - 无符号数或补码的乘法不具备这些属性
# 2.4.6 C 语言中的浮点数
笔记
- 参照 c 语言中的浮点数
编辑 (opens new window)