EPI_PrimitiveTypes_No.001_Parity

关于EPI

EPI即Elements Programming Interviews这本书，是除了CC189以外我见过最好的讲面试的书。
这本书的风格和CC189还不是完全一样，三个作者都是男性，也都是资深的软件工程师，不少分析的角度都非常独到而严谨。

问题描述

给定一个64位整型数，求其Parity，即1的个数如果是奇数，Parity=1，否则Parity=0.

思路解析

这道题要做出来不难，但可以深挖出不少做法，也算是有一定代表性。

1. 暴力破解
   所谓暴力破解，那就是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;
}

2. 稍微改进一点的解法
   上面一种解法，假如只是最高位有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;
}

3. 思维飞跃：使用哈希表
   前面两种方法都是要遍历二进制数，所以复杂度是线性的。
   在此前提下，如何提高时间效率？有一种常见的方法就是空间换时间，也就是说事先算好的结果存起来，到时候直接查表。
   那么，也就是说假如可以把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)。

4. 思维再飞跃：使用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对位运算的价值，等等。