使用与（&）运算代替取余

取余数: a%b

由于位运算比较高效，在某些情况下，当b为2的n次方时，有如下替换公式：
????????a % b = a & (b-1)? 条件是?b=2^n
????????即：a %?2^n?= a & (2^n-1)

例如：

????????14%8，取余数，相当于取出低位，而余数最大为7，14二进制为1110，8的二进制1000，8-1 = 7的二进制为0111，由于现在低位全为1，让7跟14做&运算，正好取出的是其低位上的余数。????????

1110&0111=110 即 6 =14%8；

（此公式只适用b=2^n，是因为可以保证b始终只有最高位为1，其他二进制位全部为0，减去1，之后，可以把高位1消除，其他位都为1，而与1做&运算，会保留原来的数。）

应用

看hashMap(JDK7)源码时，发现有此应用：

    /**
     * 利用Key的hash值和数组的长度（length），找到key对应在table数组中的下标
     * @param h key的hash值
     * @param length HashMap中table数组的长度
     * @return 下标
     */
    static int indexFor(int h, int length) {

        return h & (length-1);//实际上相当于h%length取余数，但&计算速度更快
    }

此处能应用这个公式，是因为HashMap源码中的数组长度使用roundUpToPowerOf2方法把map中底层数组的长度设置成2n，好像用来减少hash冲突的（是否是用来减少冲突不敢100%确定）

private void inflateTable(int toSize) {
        //为了减少hash冲突，最好把数组设置成2的n次方，此方法用于找到大于toSize的“最小的2的n次方”。
        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

        table = new Entry[capacity];

        initHashSeedAsNeeded(capacity);
    }

    //把number的设置成2的n次方
    private static int roundUpToPowerOf2(int number) {

        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }