LamのCrow HomeArchivesTagsCategories
CSAPP-2

第二章—信息的表示和处理

研究对象

  • 无符号编码基于传统的二进制表示法, 表示大于或者等于零的数字
  • 补码编码时表示有符号整数的最常见的的方式
  • 浮点数编码时表示实数的科学学计数法的以2为奇数的版本

计算机的表示法时用有限数量的位来对一个数字编码, 当结果太大时会溢出.

浮点运算有不同的数学属性

由于表示精度有限, 浮点运算是不可结合的

1
2
3
4
5
6
7
8
9
理解不可结合

0.2 + 0.3 = 0.5 四舍五入变成 1

0.2 +  0.3 + 0.5 = 1

(0.2 + 0.3) + 0.5 = 2  前面的一个四舍五入变成1, 加上后面的0.5等于1.5, 再四舍五入就是2了

结合与否可能会导致不同的答案, 所以浮点运算是不可结合的

信息存储

  • 大多数计算机使用的是8位的块, 也就是字节, 作为最小的可寻址的内存单位.
  • 内存的每个字节都由一个唯一的数字来表示, 称为它的地址.
  • 程序在运行时会划分空间来存放不同的程序对象(数据, 指令, 控制信息)

十六进制表示法(如0xb47ac3)

使用二进制来描述位模式(就把它想成一堆0101, 没有任何意义的信息, 要想让它有意义, 就要用到解释, 不同的解释使它具有不同的意义)太过冗长, 使用十进制来描述不够直观(因为最终是2进制), 所以选择了十六进制来描述位模式.

十六进制与二进制之间的转换

十六进制转二进制

使用一位拆四位的方法

1
2
3
就像是这样
十六进制     2      7      C      A      D
二进制    0010   0111   1100   1010   1101

二进制转十六进制

使用四位并一位的方法

1
2
3
就像是这样
二进制    0010   0111   1100   1010   1101
十六进制     2      7      C      A      D

十进制与二进制之间的转换

十进制转二进制

整数部分使用除二取余法, 小数部分使用乘二取整法

二进制转十进制

使用位权相加法,

如1101 = 2^3 * 1 + 2^2 * 1 + 2^0 * 1 = 13

十进制与十六进制之间的转换

十进制转十六进制

整数使用除十六取余法, 也可以先把十进制转换成二进制, 然后再转换成十六进制

十六进制转十进制

位权相加法

字数据大小

字长指明指针数据的标称大小, 因为虚拟地址是以这样的一个字来编码的(字长是一次传输的数据, 地址总线传输的也是字长, 所以指正的长度就是字的长度(如有错误, 希望指正!!))

大多数64位及其也可以运行32位程序, 这是一种向后兼容(以前的程序可以用在后来的机器, 但是后来的程序不能用在以前的机器)

C语言支持多种数据格式, 其中需要注意的使int32_t和int64_t, 它们分别为4个字节和8个字节. 它们很重要的特性就是可移植性很强(应为其他的数据再不同位的计算机中长度也不同, 但是这两个是直接规定长度, 所以在不同的机器里字长不会发生改变产生错误)

这里要提到的是, 可移植性的一个方面就是使程序对不同数据类型的确切大小不敏感.

Untitled

寻址和字节顺序

  • 对象的地址是什么(连续数据的地址在开头)
  • 在内存中如何排列这些字节(大小端)

大小端排序法

小端排序法

最低有效字节在最前面的方式(跟我们平常写的顺序相反)

大端排序法

最高有效字节在最前面的方式(就是跟我们平时写的顺序一样)

大多数Intel都只用小端, 所以一定要学会小端, 大端不学也会

注意大小端针对的是连续的数据, 数组不是大小端排序

浮点数与整数数据都对应12345编码

  • 整形数为0x00003039
  • 浮点数为0x4640E400

可以看到两个不同的编码方式的区别但是转换成二进制还是能发现一些相同的地方(跟浮点数的编码方式有关系)

Untitled

表示字符串

C语言中字符串被编码为一个以null(值为 0 )字符结尾的字符(ASCII)数组.

布尔代数简介

基本的运算符号

Untitled

上面的这些运算可以应用到位向量上

  • 位向量: 就是固定长度为ω, 由 0 和 1 组成的串

布尔代数的分配律

1
2
3
4
& 对 | 有分配律
a & (b | c) = (a & b) | (a & c)
| 对 & 也有分配律
a | (b & c) = (a | c) & (a | c)

布尔代数的加法逆元

1
2
3
4
5
6
加法中的加法逆元就是该数 * -1
如:  a + (-a) = 0
即(-a) 为 a 的逆元
在布尔代数中^运算也有逆元
逆元就是数本身, 如: a ^ a = 0
(a ^ b) ^ a = b

位向量的应用

应用之一就是用位向量白哦是有限集合

如:

1
2
3
4
5
6
a = [01101001]表示集合A = {0, 3, 5, 6}
表现方法:
a = [ 0 1 1 0 1 0 0 1]
        | |   |     |
A = { 7 6 5 4 3 2 1 0}
唯一的地方就是代表有, 为零的地方就是代表没有

位运算中的补

就是 0 变成 1 , 1 变成 0

如[100101]的补为[011010]

C语言中的位级运算

  • | 就是OR(或)
  • & 就是AND(与)
  • ~ 就是NOT(取反)
  • ^ 就是EXCLUSIVE-OR(异或)

进行位级运算建议将其他进制都转化为二进制, 然后再转化回原本的进制

异或的换位应用

1
2
3
4
5
6
//正常我们进行换位, 都需要一个临时变量, 然而使用^则不需要
int x, y;
y = x ^ y;      x= x      y = x ^ y 
x = x ^ y;      x = x ^ X ^ y = y      y = x ^ y
y = x ^ y;      x = y      y = y ^ x ^ y = x
//最终x = y , y = x

位级运算的掩码运算应用

  • 原码 & 掩码 = 结果

掩码0xFF的表示一个字的低位字节

x = 0x89ABCDEF

x & 掩码 = 0x000000EF

C语言中的逻辑运算

  • || 或
  • && 与
  • ! 非

可用于数字

1
2
3
4
5
!0x41  =  0x00
!0x00  =  0x01
!!0x41  =  0x01
0x69 && 0x55  =  0x01
0x69 || 0x55  =  0x01

逻辑运算符的特性

逻辑运算符 && 和 || 它们对应的位级运算 & 和 | 至今啊的区别是, 如果对一个参数求值就能确定表达式的结果, 那么逻辑运算符就不会对第二个参数求值. 

1
2
3
4
5
6
a && 5 / a
情况一:
a != 0, 则a真, 5 / a也为真,  表达式为真
情况二:
a == 0, 则a为假, 按常理5 / a分母为零应该报错, 因为逻辑运算符的性质, 当a为假时, 表达式已经可以
确定结果了, 所以忽略了5 / a, 直接得出了表达式为假

C语言中的移位运算

左移

二进制串会左移k位, 并在右侧补上k个 0

右移

逻辑右移

逻辑右移k位, 在左边补上k个 0

算数右移

算数右移k位, 在左边补上k个 最高位的值(就是最左边是1就补1, 最左边是0就补 0)

几乎所有有符号数都使用算数右移

移动的k大于原本数的位数

就像是只有32位的数字, 去右移34位, 这显然不合理

做出的规定是: x >>(<<) k % x的位数 = y

就像是0xFFDCBA98左移32位, 则移动0位, 因为32 % 32 = 0

移位的优先级

加减(+ -)的优先级高于位移(<< >>)

整数的表示

描述整数的两种方式

  • 只能表示非负数(x ≥ 0)
  • 能表示负数, 零和正数

引入数学语言

Untitled

各位的取值范围

Untitled

为什么正负的范围是不一样的

1
2
3
4
5
6
7
比如四位
1     0     0     0     
-8    0     0     0     得到最小值是-8
而最大值
0     1     1     1
0     4     2     1     得到最大值是7
因为再补码中正数的位始终要比负数小,  所以总是差 1

无符号数编码

就是正常的二进制编码, 使用位权相加法即可算出其值

补码编码(非常重要, 几乎所有机器都是用补码)

正如我们刚刚讨论的有符号数正负范围不相同那样

将字的最高有效位解释为负权,

举个例子就行了

1
2
3
比如四位
二进制     1     1     1     1     
代表值     -8    4     2     1

数学语言的定义(我感觉读懂就行了, 没必要深究)

Untitled

就是二进制上 0 就是 0 , 二进制上 1 就是 1 * 2^i

其实还有两种编码跟补码同等级

  • 原码, 最高位为符号位(1以及-1), 其他位正常
  • 反码, 最高位的权是-(2^ω-1 - 1)而不是, -2^ω-1(只用知道反码从原码怎么变的就行了)

无符号数与有符号数之间的转换

核心:只改变解读的方式, 不改变位模式

1
2
3
4
例子
1101 有符号数就是补码编码解释为: -3
转换为无符号数
1101 可以看到位模式还是没变(1101),但是是用无符号编码解释为:  13

补码转为无符号数

Untitled

求证过程需要的时候再回来翻书吧…….

解释一下就是如果有符号数转换成无符号数共两种情况

  • 第一种情况, x ≥ 0 这时也可把它看成无符号, 所以不用转换
  • 第二种情况, x < 0 这时加上2的位数次幂转成整数(但是大部分情况都不是-x)

需要知道的是这里的转换只是解释方式的转换, 而不是我们所说的负数变成整数, x = -x

1
十六位有符号数-12345转成有符号数为53191 == -12345 + 2 ^ 16

值得注意的是一个推论

Untitled

无符号数转换为补码

Untitled

解释

  • 当小于等于有符号数的最大值时, 无符号数转为补码不变
  • 当大于有符号数的最大值时, 无符号数 - 2^ω

这里为什么不是-2^(ω-1), 因为原本最高位的1被解释成了 2^(ω-1), 结果变成补码后被解释成了 - 2^(ω-1), 这种间就差了2 * 2^(ω-1) = 2^ω, 所以时减去2^ω.

C语言中的有符号数与无符号数

在执行一个运算时, 一个有符号, 一个无符号, 那么C会隐式地将有符号强制转化为无符号, 来执行运算(注意这个运算也包括< > ==)

扩展一个数字的位表示

无符号数的零扩展

举一个例子就好了

1
2
8位[11111111]扩展为16位
为[0000000011111111],在前面加上0即可

有符号数的符号扩展

举例子

1
2
3
4
5
6
最高位为 0 
8位[01111111]扩展为16位[0000000001111111]
最高位为 1
8位[11111111]扩展为16位[1111111111111111]

但是注意,  即使是最高位为1的扩展也不会改变该数的值的, 不懂的话就拿一个四位数验证就好了

截断数字

无符号数截断

截断高位的数字

有符号数(补码)截断

先将补码转换为无符号编码截断, 截完了再转换为补码(也是截断高位, 但是符号可能会变)

在这里我们要知道核心思想: 就是截断的是二进制的位模式, 无符号跟补码只是解释方式

整数的运算

无符号数加法

如果相加溢出, 则丢弃最高位

检验无符号数加法中的溢出

s = x + y 当 s < x(s < y)时, 发生了溢出

无符号数的加法逆元

加法逆元的定义就是x + y = 0, 则 y 就是 x 的逆元

Untitled

再无符号中x + y = 2^ω, 则 y 为 x 的逆元

补码的加法

Untitled

有点可以记一下, 就是一正一负一定不会产生溢出,

补码的非

  • x = TMIN时, 补码的非等于本身
  • x > TMIN时, 补码的非等于全位取反, 最后一位加一

无符号乘法

先转换为我们熟悉的十进制, 做完运算以后, 再变回二进制, (如果有有溢出)截断高位的

Untitled

上面的mod运算也就相当于截断前面的位

有符号(补码乘法)

先把它当成无符号来计算, 再把无符号数转换成补码就行了

乘以常数(2的幂)

相当于左移, 右边补零(不论是无符号, 还是补码)

除以常数(2的幂)

无符号数: 逻辑右移, 左边用0来补齐

有符号数(补码):向下舍入(就是往底里算)99.1 向下舍入就是99

浮点数

二进制小数

跟十进制非常想, 只是位权从10^k变成了2^k

举个例子比较好记住

1
2
3
1     1     1     1     .     1     1     1
                转换成十进制来看
8  +  4  +  2  +  1     +    1/2 + 1/4 + 1/8

一些基本的运算也跟10进制很像, 就像是小数点右移一个相当于乘以2, 小数点左移一个相当于除以2

IEEE浮点数

就跟科学计数法一样

Untitled

Untitled

根据exp的值, 被编码值可分成三种情况(其中s是符号, exp是阶码, frac是相当于小数部分)

Untitled

规格化数

在exp即不全部为0, 也不全部位1的情况, 阶码字段解释为以偏置形式表示有符号整数, E = exp - Bias

  • 为什么要有这个偏置Bias呢,?
  • 因为可以帮助增大浮点数的精度: 原本阶码位模式有八位, 可以表示的范围是1254, 也就是2^(1254), 这样的确可以表示很大的数, 但是我们要保证的是浮点数的精度, 也就是让阶码可以更小 , 所以我们引入了偏置值, 减去偏置值, 就可以有小于0的阶码(虽然不能表示更大的数了), 为了让两边正负的阶码差不多一样, 所以偏置常数设为Bias = 2^(n - 1)注意这里的n是位数, 这样阶码就是-126 ~ 127了

frac就是小数部分, 且0 ≤ frac < 1, 而尾数的定义为M = 1 + frac所以 1 ≤ M < 2; 为了节约一位的空间, 所以默认使用的是frac + 1,

非规格化的值

当exp(阶码)全部都是 0 的时候, 在这种情况的阶码值E = 1 - Bias. 尾数M = frac

  • 为什么要有非规格话的数
  • 表示数值0, 在规格化的值中, 因为默认加1, M总是 ≥ 1的, 而阶码全是0的时候, 由于M = frac, 所以frac等于0的时候, 整个浮点数也就表示0
  • 表示接近0.0的数. 这部分没看的很懂……(希望学长们能指导一下!)

第三种情况(又有两种情况)

  • 阶码全为1, 小数为0, 整个浮点数为正无穷(s = 0)或者负无穷(s = 1), 可以表示溢出的结果,像是零个数相乘溢出
  • 阶码全是1, 小数不是0, 得到值NaN(Note a Number). 他在计算机中可以表示非法的数,.

四种舍入方式

向下舍入

举个例子, 99.1—>99.0

              66.6—>66.0

             -99.1—>-100

总而言之, 就是向更小的舍入

向上舍入

举个例子, 99.1—>100

              66.6—>67

             -99.1—>-99

总而言之, 就是向更大的舍入

偶数舍入

像最接近的值舍入, 系统默认的方式, 找到一个最接近的偶数值, 可上可下, 看哪个偶数最接近

向零舍入

正数向下舍入, 负数向上舍入

C语言中的浮点数

各数据类型的转换

int —> float, 数据不会溢出(都是32位), 但是可能被舍入

int or float —> bouble, 能保留精度

double —>float, 双精度变单精度, 可能溢出变成无穷, 也可能被舍入

float or double —> int, 值会向零舍入

文章作者: LamのCrow
文章链接: http://example.com/2021/12/18/第二章—信息的表示和处理 a35d2ddeb0404db781e0a0e29bc5cc9c/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 LamのCrow！
CSAPP