面试准备-深入理解计算机系统-信息的表示与处理1

浮点运算是不可结合的（由于表示的精度有限）。比如(3.14+1e20)-1e20是0.0而3.14+(1e20-1e20)是3.14。整数虽然只能编码一个较小的取值范围，但是是准确的；浮点数虽然能编码更大的范围，但是是近似的。

二进制转十六进制转换技巧1

如果x = 2^n，且n = i + 4j，i∈[0, 3]，那么可以将x写成 i’后跟j个0。其中i=0, i’=1; i=1, i’= 2

i = 2, i’=4; i = 3, i’=8 （记忆：0001，0010，0100，1000，i表示后面0的个数）

举例：

x = 2048 = 2^11，此时n = 11 = 3 + 4 * 2，则i=3, j=2，那么写成16进制为0x800

总线：负责以定长字节块的形式传递信息。定长字节块就是字word，其字节数就是字长word size。

对于一个字长为w位的机器而言，虚拟地址的范围是0~2^w - 1，程序最多访问2^w个字节。因此，字长决定了虚拟地址空间的最大大小。

32位字长=虚拟地址空间4GB

64位机器可以运行32位机器编译的程序，这是一种向后兼容

linux> gcc -m32 xx.c

linux> gcc -m64 xx.c

前者可以在32/64位机器上运行，后者则只能在64位运行。

大端和小端是一个对象所有字节的存储方式。假设一个变量x是int型，位于地址0x100处，十六进制值为0x01234567，那么地址范围0x100~0x103的字节顺序依赖于机器。一般选择了os，字节顺序救固定了。如果使用ASCII码，字符串在任何机器都是一样的结果（不看大小端），所以str比二进制数据更具有平台独立性。

大端big endian

	0x100	0x101	0x102	0x103
……	01	23	45	67	……

小端little endian

	0x100	0x101	0x102	0x103
……	67	45	23	01	……

ASCII码适合英语文档，增加其他字母之后有了Unicode（使用4个字节编码）。UTF-8包含ASCII，每个字符用1个字节编码。Java使用Unicode表示字符串，C也有支持Unicode的库。

位运算

^ XOR，exclusive-OR，异或

布尔&对|，|对&都有分配律：

a & (b | c) = (a & b) | (a & c)

a | (b & c) = (a | b) & (a | c)

加法逆元additive inverse : x + (-x) = 0，那么-x就是x的加法逆元

a ^ a = 0 → (a ^ b) ^ a = b

C语言逻辑运算符|| && ！认为非0参数都是True（1），0是False（0）。同时，如果第一个参数就能确定表达式的结果，就不会对第二个参数求值。

x>>k 右移包括两种：逻辑右移和算术右移。前者左端要补k个0，后者是左端补k个最高有效位的值。比如x = 0110 0011，x >> 4（算术右移）= 0000 0110；x = 1001 0101 → 1111 1001

对C来说几乎所有的编译器、机器都会对有符号数使用算术右移，对于无符号数，右移必须是逻辑右移。Java则规定>>是算术右移，>>>是逻辑右移。

位移的优先级低于+

---

整数表示

机器规定的各种数据类型的取值范围不是对称的，负数比正数的范围大1。但是C语言的规定某些是对称的（char short int）。而且C可以用2个字节实现int。C和C++支持有符号（默认）和无符号数，但Java只支持有符号数。

$$对向量\vec{x}=[x_{w-1},x_{w-2},...,x_0],B2T_w(\vec{x})=-x_{w-1}{2}^{w-1}+\sum _{i=0}^{w-2}{x}_i{2}^i$$

补码： two’s-complement。最高有效位称为符号位，解释为负权negative weight（-2^(w-1)），也就是说，这个最高位是1表示值为负。举例：

B2T4([0101]) = 5, B2T4([1101]) = -8 + 4 + 1 = -3

因此，w位有符号数，最大值应该是2^{(w-1)-1，最小值是-2}(w-1)。举例：对于4位有符号数，最大值应该是0111（符号位是0，剩余都是1），也就是7；最小值应该是（符号位为1，剩余都是0，这样不会有加值），也就是-8。这就是机器规定的有符号数的取值范围是不对称的原因。

数	字长w
U是无符号	8	16
UMax	0xFF 255	0xFFFF 65535
TMin	0x80 -128	0x8000 -32768
TMax	0x7F 127	0x7FFF 32767
-1	0xFF	0xFFFF
0	0x00	0x0000

注意：

1）-1和UMax是一样的，都是全1串

2）UMax = 2TMax + 1

反码：One’s Complement，除了最高有效位的权是$-(2^{w-1}-1)$外，与补码一样。反码的来源是，用[111…1]-x来计算-x的反码表示，其实也就是直接按位反转。例如：

0101 = 5，w=4，则-5 = 1111 - 0101 =1010 = -1x(2^3-1)+2=-5

$$B2O_w(\vec{x})=-x_{w-1}(2^{w-1}-1)+\sum _{i=0}^{w-2}{x}_i{2}^i$$

原码：Sign-Magnitude，最高有效位是符号位，不参与计算，用剩下的位计算值

$$B2S_w(\vec{x})=(-1{)}^{x_{w-1}}\cdot (\sum _{i=0}^{w-2}{x}_i{2}^i)$$

需要注意的是，几乎所有现代机器都使用补码。

而且这两种表示方法中，[000…0]都是+0，但反码中，[111…1]表示为-0；在源码中，[10…0]表示为-0，所以对于0都是由两种表示方式的。

C语言实现数据类型的强制转换时，是改变了解释位的方式。

补码转无符号数

$T2U_w(x)=\left\{\begin{array}{r}x+2^w,x<0\\ x,x\ge 0\end{array}\right\}$，其中w是字长