这篇文章是csapp第二章第一节的阅读笔记。

机器级的程序把内存当做一个大数组，数组里的元素就是字节。

接下来就应该看看，编译器和运行时系统是如何把由一块块字节组成的信息翻译成它本来的养子。

1 十六进制表示法

在C语言中，我们可以通过0x或0X前缀来表明一个常数是通过十六进制表示的。

二进制和十六进制的转换：很简单但是很重要。

如果一个数$x$是2的幂次数，即$x=2^n$，这里$n$是一个非负数。把这样的十进制数转换成十六进制数有一个简单的方法。先分解$n$，令$n=i+4j$，其中$0≤i≤3$，通过$x$就可以确定对应十六进制数的最高位了：1($x=0$)，2($x=1$)，4($x=2$)，8($x=8$)。然后确定最高位后面有几个0 ：这个和$j$有关，$j$是几，后面就有几个0。

比如$x=2048=2^{11}$，那么$n=11=3+4·2$，所以$i=3, j=2$，所以2048=0x800。

同样，对于十进制和十六进制的转换也很简单很重要。

2 字数据大小

计算机系统内部通过总线进行数据传输，总线的大小通过字word来指示，不同的计算机系统字的大小不同。这个字的大小也指明了指针数据的大小。最重要的，字的大小也决定了虚拟内存的空间大小。

比如，在一个计算机系统中，字的大小是$w$，那么对应的虚拟内存空间大小就是从0到$2^w-1$，一共$2^w$字节。

对于32位计算机，虚拟内存大小是$2^{32}$，大概是$4×10^9$字节，也就是4GB；对于64位的计算机，可以表示$1.84×10^{19}$字节。

64位机器上编译的程序可以在32位机器上运行，但是反过来不可以。可以通过下面的参数来指定编译：

gcc -m32 prog.c

这样编译的程序可以运行在32位和64位的机器上。

gcc -m64 prog.c

而这样编译的程序只能运行在64位的机器上。

C语言支持多种数据类型，下表列出了不同数据类型在不同的位的机器上所需的大小：

所以，最好使用固定位数的类型，比如int32_t等。

3 寻址和字节序

如果一个程序对象需要多个字节来表示，那么就需要解决两个问题：

1. 如何表示这个对象的地址；
2. 多个字节如何在内存中进行排序。

在内存中，一个程序对象的所有字节都是连续存储的，通常我们使用那个连续内存中最小的那个作为整个对象的地址。比如一个int类型的变量x，如果它的地址是0x100，那么存储这个变量的所有空间就是0x100，0x101，0x102和0x103。

对象的地址解决了，那么如何排列所有的字节呢？这就涉及到字节序的问题了。

不同的计算机系统使用不同的字节序，主要有大端字节序（big endian）和小端字节序（little endian），如图：

两者的区别就是：一个数的最低位是在所占空间的最小地址（小端）还是在所占空间的最大地址（大端）。

比如一个数0x1234567，我们的书写习惯、打印还有代码中，从左到右都是最高位（01）到最低位（67）排列，但是在内存中不一样。如果这个变量的地址是0x100，对于大端字节序，最低位67占据了所占空间的最大地址0x103；而对于小端字节序，最低位67占据了最低地址0x100。

如果内存空间是从左到右变大，那么大端字节序的排列适合我们的书写习惯一样的。

一般来说，程序员是不用关注这个字节序的，计算机会自动处理好这个问题。但在一些涉及到底层的编程中，需要注意字节序：

1. 网络编程。网络编程中涉及到不同计算机系统中的数据传输，这样就涉及到了字节序的问题，需要对不同字节序进行转换才能正确处理数据；
2. 涉及到汇编代码的时候。这里对于数字常量需要注意字节序；
3. 当程序使用类型转换来规避正常的类型系统的时候。

下面的代码可以演示所处系统的字节序：

#include <stdio.h>

typedef unsigned char *byte_pointer;

void show_bytes(byte_pointer start, size_t len) {
    size_t i;
    for(i = 0; i< len; i++) 
        printf(" %.2x", start[i]);
    printf("\n");
}

void show_int(int x) {
    show_bytes((byte_pointer) &x, sizeof(int));
}

void show_float(float x) {
    show_bytes((byte_pointer) &x, sizeof(float));
}

void show_pointer(void *x) {
    show_bytes((byte_pointer) &x, sizeof(void *));
}

void test_show_bytes(int val) {
    int ival = val;
    float fval = (float)ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}

int main() {
    test_show_bytes(123456);
    return 0;
}

结果：

 39 30 00 00
 00 e4 40 46
 6c cd 01 9e fe 7f 00 00

123456用十六进制表示就是0x3093，所以我这个机器是小端字节序。

4 字符串的表示

C语言中的字符串就是一个字节数组然后使用null结尾。所以对于一个字符串"12345"，如果调用函数show_bytes("12345", 6)的话，那么结果将是31 32 33 34 35 00。

但是对于strlen()函数来说，是不算最后的null的。所以strlen("12345")的结果是5。

由此可以得出一个结论：文本文件比二进制文件更加平台独立。

5 代码的表示

当我们写完一段代码，并将其编译成可执行程序后，不同的计算机系统所编译出来的内容是不同的，即使我们的程序是一样的。

但所编译出来的内容，都是一个字节序列。

所以从计算机的角度来说，所有的程序，都只不过是一段字节序列，或长或短而已。

6 布尔代数简介

计算机逻辑计算的即使就是布尔代数。这部分比较简单，但也很重要。

基本的布尔运算有：与（&）、或（|）、非（~）和异或（^）。

其实异或也可以使用其余的运算来表示：x^y = ~x&y | x&~y。

比如：2^3 = 10B ^ 11B = ~10B&11B | 10B&~11B = 01B&11B | 10B&00B = 01B | 00B = 01B = 1。

7 C语言中的位运算

C语言中的位运算也是很有意思，比如不使用额外的变量来交换两个数：

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

基于上面的函数，翻转一个数组：

void reserve_array(int a[], int cnt) {
    int first, last;
    for(first = 0, last = cnt - 1; first < last; first++, last--) {
        inplace_swap(&a[first], &a[last]);
    }
}

位运算的一个重要用途就是掩码（masking）。比如对一个32位系统来说：

1. 只保留x的最后一个字节，其余的置零：x&0xff；
2. x的最后一个字节保留，其余的置为对应的补数：x^~0xff；
3. x的最后一个字节置零，其余的不变：x|0xff。

8 C语言中的逻辑运算

C语言中的逻辑运算有：与（&&）、或（||）和非（!）。

这个逻辑运算和位运算有些不同，因为逻辑运算的结果只有0和1，对于传入的参数，也只认为是0（参数值就是0）或1（参数值非0）。

所以，!0x41=0x00，!0x00=0x01，!!0x41=0x01，0x69&&0x55=0x01，0x69||0x55=0x01。

逻辑运算和对应的位运算的第二个不同，在于当第一个参数就能够确定运算结果的时候，就不会计算第二个参数的值。

所以，表达式a&&5/a不会出零除错误；同样表达式p&&*p++也不会有空指针错误。

那么，如何用位运算表示x==y的结果呢？!(x^y)。

9 C语言中的移位运算

移位运算有左移和右移。

对于左移，很好理解，比如左移4位，就是去掉最高的4位，然后最低的4位用0补。

对于右移，有些不同。同样是将最低的4位去掉然后最高的4位补齐，那是用0补呢还是用1补？

两种右移：逻辑右移（logical）和算术右移（arithmetic）。

如果逻辑右移，那就用0补；如果是算术右移，取决于原来数的最高位，如果最高位是1就用1，是0就用0。

比如x=01100011，那么逻辑右移4位就是00000110B，算术右移4位就是00000110B；

当x=10010101B，那么逻辑右移4位就是00000110，算术右移4位就是11111001B。

在C语言中，对于有符号数字，使用的是算术右移；对于无符号数字，使用的是逻辑右移。

对于Java，可以通过不同的运算符来指定：>>就是算术右移而>>>就是逻辑右移。

如果一个数本身是32位，但是移动的位数大于32位，那么实际移动的位数就是取模的数。

最后需要注意的是，移位运算符的优先级低于加减，所以混合运算的时候，最好加上括号。