关于EPI
EPI即Elements Programming Interviews这本书，是除了CC189以外我见过最好的讲面试的书。
这本书的风格和CC189还不是完全一样，三个作者都是男性，也都是资深的软件工程师，不少分析的角度都非常独到而严谨。
问题描述
给定一个64位整型数，求其Parity，即1的个数如果是奇数，Parity=1，否则Parity=0.
思路解析
这道题要做出来不难，但可以深挖出不少做法，也算是有一定代表性。
- 暴力破解
所谓暴力破解，那就是1位1位地试，然后用一个数来存1的个数。这样做的话时间复杂度是O(n)，n是数字的2进制有效位数。
public static short parity(long x) {
short result = 0;
while (x != 0) {
result ^= (x & 1);
x >>>= 1;
}
return result;
}
- 稍微改进一点的解法
上面一种解法，假如只是最高位有1个1，也要数遍所有位数。所以，改进一下，每次解决1个1，那么假如有s个1，复杂度就是O(s)：
public static short parity(long x) {
short result = 0;
while (x != 0) {
result ^= 1;
x &= (x - 1); // Drops the lowest set bit of x.
}
return result;
}
- 思维飞跃：使用哈希表
前面两种方法都是要遍历二进制数，所以复杂度是线性的。
在此前提下，如何提高时间效率？有一种常见的方法就是空间换时间，也就是说事先算好的结果存起来，到时候直接查表。
那么，也就是说假如可以把64位Parity所有可能的情况都存起来，那么查表的时间复杂度就是O(1)。
当然，这样需要太大空间。可以适当削减一下，比如只保存16位整数的Parity，那么64位分成4个16位然后分别查表组合起来就行：
public static short parity(long x) {
final int WORD_SIZE = 16;
final int BIT_MASK = 0xFFFF ;
return (short) (
precomputedParity[(int)((x >>> (3 * WORD_SIZE)) & BIT_MASK)]
^ precomputedParity[(int)((x >>> (2 * WORD_SIZE)) & BIT_MASK)]
^ precomputedParity[(int)((x >>> WORD_SIZE) & BIT_MASK)]
^ precomputedParity[(int)(x & BIT_MASK)]);
}
不失一般性，设word_size为L，那么时间复杂度就是O(n/L)。
- 思维再飞跃：使用Parity特性
在上面一种解法中，我们使用异或将不同部分的结果组合起来。道理也很简单，稍微思考一下就能明白。而利用这个特性，有一种O(logn)且不借助哈希表的解法，就是不断地折半异或：
public static short parity(long x) {
x ^= x >>> 32;
x ^= x >>> 16;
x ^= x >>> 8;
x ^= x >>> 4;
x ^= x >>> 2;
x ^= x >>> 1;
return (short) (x & 0x1);
}
总结
恢复刷题，因此选择一个不是很难的问题。但同时这道题里面也蕴含着许多位操作的相关手段，例如如何抽离最低位的1，Hashmap对位运算的价值，等等。
