编程珠玑第一章探讨

第一章陈述了一个算是在特定领域很好用的方法，中学时上编程课老师给出了这种方法，题目是一串不会重复的数字，最大的数字不会超过某个值，要求排序输出。其实根本不需要真去做排序，当时用Pascal语言的boolean数组很容易就解决了这个问题。也就是跟本章提到的位向量异曲同工。显然如果除了算法与数据结构外其他条件都一样的情况下，线性的算法要明显优于O(NlogN)的基于比较的排序算法。作者给出了问题本质和使用范围：

该数据结构描述了一个有限定义域内的稠密集合

问题探讨

2.这道题目让我学会了int类型的位向量实现思路是什么，老实说我以前从没考虑过用位运算，要是我的话，估计直接上bool数组了。

//基于编程珠玑原始程序
#define SHIFT 5
#define MASK 0x1F
#define N 10000000
int a[1 + (N >> SHIFT)]; // equal to (N/32)

void set(int i) {        a[i >> SHIFT] |=  (1 << (i & MASK)); }
void clr(int i) {        a[i >> SHIFT] &= ~(1 << (i & MASK)); }
int test(int i) { return a[i >> SHIFT] &   (1 << (i & MASK)); }

4.这题我很喜欢，生成随机数据不必要真的生成，对于本题目，正确的做法是打乱本来有序的数据。

9.我从来没有想过类似的问题，解决方案是多道保险。一个top代表已经初始化了几个数字，从0开始。from数组代表当前被访问的i位置上是第top个被初始化的；to数组代表第top个被初始化的是i位置上的。这样的话必须满足

from[i] < top && to[from[i]] == i

才能说明被初始化了，而内存中的随机值要达到上面的条件几乎不可能。

from[i] = top
to[top] = i
data[i] = 0
top = top + 1

这个技术在哪里有实用的意义呢？(资源寸土寸金的航天飞机上？)

12.这道题目让我想起了《3 idiots》这个电影，事实上早期真的是用铅笔解决问题的，但是确实危险，在失重环境下，铅笔的粉尘漂浮于精密的飞船中是一个不可想象的可怕情况。不过，本书作者在深入阅读中也提到了这个问题目的是要求我们打破概念壁垒。这是好的，打破思维的壁垒能让我们更容易看破一些问题，也就是典型的Hack思维方法。不过，Hack the problem不等同于Solve the problem。归根结底，宇航员还是要用几百万美元研发成本的太空笔，因为那是真正的解决了问题，「铅笔」这种想法只是绕过了问题，有这种意识挺好，说不定什么时候能帮上大忙。但是小聪明归小聪明，我们终究还是要踏踏实实的去解决问题的。

摘录

Chuck Yeager将军(第一个超音速飞行的人)赞扬一架飞机的机械系统时用的词是「结构简单、部件很少、易于维护、非常坚固」。

Antonine de Saint-Exupéry是法国作家兼飞机设计师，他曾经说过：「设计者确定其设计已经达到了完美的标准不是不能再增加任何东西，而是不能再减少任何东西。」