信息存储
大多数计算机使用8位的块, 或者字节, 作为最小的可寻址的内存单位,而不是访问内存中单位的位. 机器级程序将内存视为一个非常大的字节数组,称为虚拟内存(virtual memory). 内存的每个字节都由一个唯一的数字来标识, 称为它的地址(address), 所有可能地址的集合就称为虚拟地址空间(virtual address space)
十六进制表示法
在计算机中, 用十六进制(简写为”hex”)数来表示位模式.
一个字节由8位组成, 在二进制表示法中, 它的值域的00000000
11111111.若看成十进制整数, 它的值域就是0255.两种符号表示法对于描述位模式来说都不是非常方便. 二进制表示法太冗长, 而十进制表示法与位模式的相互转化很麻烦.
字数据大小
每台计算机都有一个字长(world size), 指明指针数据的标称大小. 因为虚拟地址是以这样的一个字来编码的, 所以字长决定的最重要的系统参数就是虚拟地址空间的最大大小. 也就是说, 对于一个字长为w伟大机器而言, 虚拟地址的范围为
1 | 0~2^w-1, 最大访问2^w个字节 |
寻址和字节顺序
对于跨越多字节的程序对象, 我们必须建立两个规则: 这个对象的地址是什么, 以及在内存中如何排列这些字节. 在几乎所有的机器上, 多字节对象都被存储为连续的字节序列, 对象的地址为所使用字节中最小的地址.
最低有效位和最高有效位
考虑一个w位的整数，其为表示为
1 | [x_{w-1}, x_{w-2}, ```, x_1, x_0] |
按从左至右顺序看, 第一位是最高有效位, 最后一位为最低有效位.
举个例子, 假定w=8, 即一个字节大小. 7的二进制原码为0000 0111,其中 从左至右,第一个0是最高有效位, 最后一个1为最低有效位.
最高有效字节和最低有效字节
跟最低\高有效位的意思相近, 假设w是8的倍数, 这些位就能被分组成为字节(每8个二进制位为一个字节), 从左至右看, 最高有效字节就是第一个二进制位分组的字节. 最低有效位字节就是最后一个二进制位分组的字节.
大端法(big endian)和小端法(little endian)
按照最低有效字节到最高有效字节的顺序存储对象, 即低位字节放低地址的方式称为小端法
按照最高有效字节到最低有效字节的顺序存储对,象高位字节放低地址则称为大端法
布尔代数简介
4个基本的布尔运算: ~非, &与, |或, 异或^
位向量的运算, 位向量就是固定长度位w, 有0和1组成的串. 位向量的运算可以定义成参数的每个对应元素之间的运算.
1 | 举一个例子, 假设w=5, 参数a=[0110], b=[1100]. 那么4种运算a&b, a|b, a^b, 和~b分别得到以下结果: |
关于布尔代数和布尔环的更多内容
对于任意整数w>0, 长度为w的位向量上的布尔运算|, &和~形成了一个布尔代数. 最简单的情况是w=1时, 只有2个元素; 但是对于更普遍的情况, 有2的w次方个长度为2
的位向量.布尔代数和整数运算符有很多相似之处. 例如, 乘法对假发的分配律, 写为a·(b+c) = (a·b)+(a·c), 而布尔运算&对|的分配律,写为a&(b|c)=(a&b)|(a&c), 此外, 布尔运算|对&也有分配律, 写为a|(b&c)=(a|b)&(a|c)
当考虑长笛为w的位向量上的^, &和~运算时, 会得到一种不同的数学形式,我们称为布尔环. 布尔环与整数运算有很多相同的属性. 例如, 整数运算的一个属性是每个值x都有一个加法逆元-x, 使得x+(-x)=0,布尔环也有类似的属性, 这里的”加法”运算是^, 不过这时每个元素的加法逆元是它自己本身. 也就是说, 对于任何值a来说, a^a=0
移位运算
左移
对于w位的操作数x, x向左移动k位, 丢弃最高的k位, 并在右端补个0.
右移—逻辑右移,算数右移
- 逻辑右移
- 向右移动k位, 在左端补k个0
- 算数右移
- 向右移动k位, 在左端补k个最高有效位的的值
比如
| 操作 | 值 |
|---|---|
| 参数x | [01100011] [10010101] |
| x<<4 | [00110000][01010000] |
| x>>4(逻辑右移) | [00000110] [00001001] |
| x>>4(算术右移) | [0000110] [11111001] |
有符号数与无符号数之间的转换
强制类型转换的结果保持位值不变，只是改变了介绍这些位的方式。
比如4位的无符号数转4位的有符号数
1111(十进制为15) -> 转为为有符号数 -> 1111(十进制为-7)
扩展一个数字的位表示
- 对于无符号数而言, 要将一个无符号数转换位一个更大的数据类型,只要简单地在表示的开头添加0(扩展多少位,就在原有二进制数的基础上在前面加0扩充到多少位)
- 对于补码数字而言, 可以执行一个符号扩展, 在表示中添加最高有效位的值.(跟无符号数相似, 若补码数字大于等于0, 跟无符号数的方式相同, 若是负数,则把扩充的0换成1)
截断数字
- 对于无符号数而言, 要将一个w位的数截断为一个k位的数字, 则丢弃高位w-k位.
- 对于补码截断, 跟无符号数有相似的属性,只不过要将最高位转换位符号位(即截掉后高位是1就是负数,是0就是正数).
整数运算
无符号加法/乘法
跟日常的代数运算相同,但对于出现溢出的情况则是算出的结果丢弃最高位,直接截断
比如当w=4时, 1001 + 1100 = 10101, 结果超出4位,需要截断,截掉最高位的数, 即结果位0101
补码加法/乘法
跟无符号加法一样, 溢出就截掉高位
乘于整数
以往, 在大多数机器上, 整数乘法指令相当慢, 需要10个或者更多的时钟周期, 然而其他整数运算(例如加法, 减法, 位级运算和移位只需要1个时钟周期.)即使在现在, 其整数乘法夜需要3个时钟周期, 因此,编译器使用了一项重要的优化, 试着用移位和加法运算的组合来代替乘以常数因子的乘法.
3.