最近开始读《深入理解计算机系统》这本书。对于书中提到的从程序员的角度解读计算机系统这一说法非常感兴趣，所以决定好好读一读。从开始接触计算机编程就是站在一个高级语言的层次，虽然对编译原理，操作系统，汇编语言和计算机组成原理都有所了解，但总觉着所有的知识都还停留在书本上，很难把这些东西都梳理到一个系统中。虽然有一些原理上的知识，但对于我来说更喜欢了解一些细节知识以增加我理解深度。希望通过阅读这本书可以增加这方面的理解，更好地理解计算机到底是如何工作的，这样对以后的编程工作也应该是有帮助的吧。

 

　　刚刚看完的是关于位操作的一些内容，在这里做一些记录以备以后回来复习，主要都是一些我认为对于我之后编相关程序时会有提点作用的内容。下面内容中加引号是对原书中一些句子的直接引用。

1.用位向量表示有限集合

　　“位向量的一个很有用的应用就表示有限集合”。例如用n个二进制位便可以表示一个n元集合的所有子集。

　　读完这一部分，我有两种理解。其一是：将二进制的每一位数据对应于我们要分析的集合中的一个元素，有和没有分别对应于1和0，通过这样的对应关系，最大的好处就是可以枚举那些本来不便于枚举的集合，方法就是将位向量转化为对应的十进制数。

　　对于位向量我的另一个理解是，因为n位二进制可以表示2^n个数，所以，如果将这2^n个数映射到一组元素，也就实现了n位二进制数对集合元素的映射。和上面那种的区别在于，上面的那种是一位对应一个元素，而现在是一个向量对应于一个元素。之所以会这么想是因为想到了之前看过的一道面试题。大概内容是现在有8瓶药水，其中有一瓶是有毒的，现在要用小白鼠做实验检查哪一瓶有毒，问最少需要几只小老鼠。

　　这个问题的答案是：3只 。方法是准备三个空杯子标记为0,1,2，将8瓶药水按序号转化为二进制后，对应位为一，则在对应序号的杯子中假如这种药水。最后将这三杯药水分别给三只小白鼠喝下，根据小老鼠的反应，通过二进制找到对应的水杯。例如对于第三瓶药水，二进制为’011‘，则在第0,1两个杯子中加入药水。如果这瓶药水是有毒的，则喝下0,1两杯药水的小白鼠会出现反应。最终通过将小白鼠对应于二进制向量，可以得到对应的有毒的药水的序号。这个问题我觉着就是典型的将二进制向量与集合元素相对应的问题。对于类似的问题，应该算是一个启发。另外如果推广一下也可以将有三个状态的事物对应于三进制位等等等等。

　　原书中还提到了对于位向量对应有限集合的问题，“布尔运算|和&分别对应于集合的并和交”。在计算机系统中对这个知识也有广泛的应用，其中之一就是掩码，通过二进制掩码可以实现对一些位数据的屏蔽，比如我们非常熟悉的网络中的子网掩码。

2.通过异或实现元素的交换

　　在实现两元素交换值这一问题上，异或无疑是很好的方式，最大的好处就是不需要申请辅助空间，可以实现原地交换。实现代码如下（原书代码）：

1 void inplace_swap(int *x, int *y)2 {3 　　*x = *x ^ *y;4 　　*y = *x ^ *y;5 　　*x = *x ^ *y;6 }

　　这里写这个是希望记下两点，一是“对于任意向量a，有a^a=0”。正是因为有这个特性，才有了上面的结果。

　　另一个需要记下的是下面这样一个问题。在原书中有这样一个例子：利用上面的inplace_swap函数，我们可以实现一个数组中的元素头尾两端依次对调的函数（原书代码如下）：

1 void reverse_array(int a[], int cnt)2 {3     int first,last;4     for(first = 0, last = cnt-1; first<=last; first++,last--)5     {6         inplace_swap(&a[first], &a[last]); 7  } 8 }

 　　刚看到代码并没有看出任何问题，这是非常简单的一段代码。但是如果我们执行他并给a数组赋值{1,2,3,4,5}，我们得到的答案将是{5,4,0,2,1}。我们简单分析一下就能知道会得到这样的结果的原因是在first==last是，我们传递给inplace_swap函数传递的两个参数指向了同一片地址空间（注意不是值相等，而是地址相同），这样在执行(*x = *x ^ *y)这行代码时，由于地址相同，*x和*y同时变为0，这样后面两次操作不管怎么弄，都不会等于其他的了。这也就告诉我们一个需要注意的点：在使用异或操作实现变量交换时，不能出现交换同一地址上值的情况。当然啦，要解决上面这个问题很简单，只要将for循环的条件改为（first<last）就行了。