Charpter Two 信息的表示和处理
2017-10-24 本文已影响0人
1nfinity
- 2.1 信息存储
- 2.1.4 表示字符串
- 独立性(文本数据/二进制数据)
- 文本数据比二进制数据具有更强的平台独立性
- 原因: 在使用ASCII码作为字符码的任何系统上都将得到相同的结果
- 文本数据比二进制数据具有更强的平台独立性
- 独立性(文本数据/二进制数据)
- 2.1.6 布尔代数简介
- 位向量
- 定义: 位向量是固定长度为w, 由0和1组成的串
- 应用:
- 表示有限集合
- 例:
- a = [01101001] 表示 A = {0, 3, 5, 6}
- a = [01010101] 表示 A = {0, 2, 4, 6}
- 布尔运算|和&分别对应于集合A的交与并, 而~对应于集合的补
- 例:
- 表示有限集合
- 分配律:
- &对|: a&(b|c) = a&b|a&c
- |对&: a|(b&c) = a|b&a|c
- 加法逆元:
- a^a = 0
- (ab)a = b
- 位向量
- 2.1.7 C语言中的位级运算
- 掩码:
- 定义: 掩码是一个位模式, 表示从一个字中选出的位的集合
- 例: 假设 x = 0xEDFCA3423, x&0xFFLE可以提取出x的最低八位字节, 即提取后的值为: 0X00000023
- 按位取补: 即按位取反, 运算符为: "~"
- 掩码:
- 2.1.8 C语言中的逻辑运算
- 注意:
- 逻辑运算很容易与位级运算相混淆, 但它们的功能是完全不同的
- 逻辑运算认为所有==非零==(包括1)的参数都表示TRUE, 参数0表示FALSE. 它们返回0或者1
- 注意:
- 2.1.9 C语言中的移位运算
- 补充知识:
- 操作数: 操作数是运算符作用于的实体，是表达式中的一个组成部分，它规定了指令中进行数字运算的量
- 移位运算的结合性
- 移位运算是从左至右可结合的, 所以x<<j<<k == (x<<j)<<k
- 右移运算有两种
- 逻辑右移: 左端补上n个0
- 算术右移: 左端补上n个最高位
- 注意:
- C语言没有明确定义使用哪种类型的右移, 而Java明确规定算术右移使用x<<j, 逻辑右移使用x<<<j
- 几乎所有的编译器使用算术右移
- 移动k位, k大于位数w:
- C语言未规定, Java明确规定位移数量应该按照我们前面所讲的求模(mod)方法来计算
- 求模方法(mod): 求余数, 特别: 3mod5 = 3
- C语言未规定, Java明确规定位移数量应该按照我们前面所讲的求模(mod)方法来计算
- 补充知识:
- 2.1.4 表示字符串
- 2.2 整数表示
- 2.2.1 整数类型数据
- 固定大小数据类型:
- int32_t/int64_t: 为了平台的可移植性而设计的固定位长的数据类型, 分别为32位/64位
- 固定大小数据类型:
- 2.2.2 无符号数的编码
- 定理: 无符号数编码具有唯一性, 即其二进制表示和十进制表示是一一对应的
- 中英文对比:
- 补码: two's-complement
- 负权: negative weight
- 解释: 有符号数中字的最高有效位
- 反码: ones'complement
- 注意: 补码(two' complement)和反码(ones'complement)中撇号("'")的位置是不同的
- 原因: 见原书P48
- 注意: 补码(two' complement)和反码(ones'complement)中撇号("'")的位置是不同的
- 2.2.4 有符号数和无符号数之间的转换
- 规则(一般): 数值可能会改变, 但是位模式不变
- 当将一个有符号数映射为它相应的无符号数时, 负数会被转换成大的正数, 而非负数会保持不变
- 规则(一般): 数值可能会改变, 但是位模式不变
- 2.2.5 C语言中的有符号数和无符号数
- 默认: 声明整数时, 一般默认是有符号数. 例: 12345
- 无符号常量: 在后面添加"U"或"u", 例: 12345U
- 奇特的行为:
- 当执行一个运算时, 如果它的一个运算数是==有符号的==而另一个是==无符号的==, 那么C语言会隐式地将有符号参数强制类型转换为无符号数, 并假设这两个数都是非负的
- 默认: 声明整数时, 一般默认是有符号数. 例: 12345
- 2.2.6 扩展一个数字的位表示
- 分类
- 无符号数:
- 扩展类型: 零扩展(zero extension)
- 定义: 简单地在数值的开头添加0
- 扩展类型: 零扩展(zero extension)
- 补码数:
- 扩展类型: 符号扩展
- 定义: 在数值的开头添加最高位的值
- 扩展类型: 符号扩展
- 无符号数:
- 类型和大小的同时转换
- 原则(C语言规定): 先进行大小转换再进行类型转换
- 分类
- 2.2.7 截断数字
- 分类:
- 无符号数:
- 原理: 直接截断
- 补码数:
- 原理: 截断后把最高位转换为符号位
- 无符号数:
- 分类:
- 2.2.8 关于有符号数和无符号数的建议
- 绝不使用无符号数
- 原因: 有符号数到无符号数的隐式转换会导致错误或漏洞
- 绝不使用无符号数
- 2.2.1 整数类型数据
- 2.3 整数运算
- 2.3.1 无符号加法
- 原理: 当无符号数之和溢出时, 会丢弃溢出的位
- 检测溢出
- 方法: 对在范围 0<=x, y<=UMax 中,令 s = x + y. 则当且仅当s<x(或等价的s<y)时, 发生溢出
- 推导: 很简单, 利用结果超过UMAx会溢出的特性可轻松求得
- 方法: 对在范围 0<=x, y<=UMax 中,令 s = x + y. 则当且仅当s<x(或等价的s<y)时, 发生溢出
- 无符号数求反
- -x = 2^w - x
- 2.3.2 补码加法
- 原则: 范围必须在 -2^w ~ 2^w 之间
- 2.3.3 补码的非
- bug: 由于求反的数是关于0对称的, 而补码的范围则是非对称的(-a <= x < a), 因此在x = -a即x = TMin时, -x不等于 -TMin, 而是由于溢出等于 Tmin
- 小贴士:
- 使用一个十六进制数字 a 表示长度w = 4的位模式时, a 里面已经包含了正负号的信息, 所以这个数字一定是非负数
- 2.3.7 除以2的幂
- 负数除法的偏置
- 在通过移位计算除法时, 需要偏置这个值, 偏置的大小为2^k - 1
- 偏移技术的使用范围:
- 偏移技术只适用于负数, 如果用于正数, 则除不尽的结果会比正确值大1
- 除以2的幂可以通过逻辑或算术右移来实现, 但这种方法不能推广到除以任何常数
- 负数除法的偏置
- 2.3.8 关于整数运算的最后思考
- 计算机执行的"整数"运算实际上是一种模运算形式
- 模运算表示了数字的有限字长限制了可能的值的取值范围, 结果运算可能溢出.
- 计算机执行的"整数"运算实际上是一种模运算形式
- 2.4.2 IEEE浮点表示
- 表示形式:
- V = (-1)s * M * 2E
- 符号(sign): s决定这个数是正还是负, 对数值0做特殊处理
- 尾数(significand): M是一个二进制小数, 范围为: 1~2-ε, 或者0~1-ε
- 阶码(exponent): E的作用是对浮点数加权
- V = (-1)s * M * 2E
- 表示形式的编码:
- 一个单独的符号位s直接编码符号s
- k位的阶码字段exp=ek-1...e1e0编码阶码E
- n位小数字段frac=fn-1...f1f0编码尾数M, 但编码的值也依赖于阶码字段的值是否等于0
- 根据exp的值不同分为的三种情况:
- 情况1: 规格化的值
- exp不全为0, E = e - Bias, Bias = 2k-1 - 1, M = 1+ f (0<=f<1>>)
- 情况2: 非规范化的值:
- exp全为0, E = 1 - Bias, M = f
- 情况3: 特殊值
- exp全为1
- 小数域全为0, 表示无穷大
- 小数域不为0, 表示"NaN"
- exp全为1
- 向偶舍入:
- C语言默认使用向偶舍入
- 原则: 舍入到最接近的值, 如进行舍入的值处于两个可能结果的正中间,则按使结果的最低有效数字是偶数的方向舍入
- 注意:
- 1.555/2.555在C语言中的舍入结果是不一样的, 前者结果为1.55, 后者结果为2.56
- 原因: 1.555在浮点数中的最精确表示为:1.55499994754791259765625E0, 2.555则为: 2.5550000667572021484375E0. 根据向偶舍入的原则,1.555舍入为1.55, 2.555舍入为2.56
- 1.555/2.555在C语言中的舍入结果是不一样的, 前者结果为1.55, 后者结果为2.56
- 情况1: 规格化的值
- 必须小心的使用浮点运算, 因为浮点运算只有有限的范围和精度, 而且并不遵守普遍的算术属性
- 表示形式:
- 2.3.1 无符号加法
