与操作代替取模操作

$m \bmod a^{k}$ 就是 $m$ 在 $a$ 进制下的低 $k$ 位。

十进制

$a = 10$

十进制
$1\textcolor{red}{5} \bmod 10 = \textcolor{red}{5}$
$1\textcolor{red}{50} \bmod 100 = \textcolor{red}{50}$

十进制对整百整千的取模操作，对人来说，压根就不用算，直接就能往外报答案，报的不就是后面那几位么，那其他进制呢？

其他进制

四进制

$a = 4$

四进制	十进制
$10\textcolor{red}{1} \bmod 10 = \textcolor{red}{1}$	$17 \bmod 4 = 1$
$2\textcolor{red}{22} \bmod 100 = \textcolor{red}{22}$	$42 \bmod 16 = 10$

可以发现上面的 $\textcolor{red}{1} , \textcolor{red}{22}$ 都是可以通过观察直接得到的，就是截断了前面的数的低 $\textcolor{red}{k}$ 位。

三进制

$a = 3$

三进制	十进制
$12\textcolor{red}{1} \bmod 10 = \textcolor{red}{1}$	$16 \bmod 3 = 1$
$1\textcolor{red}{21} \bmod 100 = \textcolor{red}{21}$	$16 \bmod 9 = 7$

可以发现上面的 $\textcolor{red}{1} , \textcolor{red}{21}$ 都是可以通过观察直接得到的，就是截断了前面的数的低 $\textcolor{red}{k}$ 位。

二进制

$a = 2$

二进制	十进制
$111\textcolor{red}{1} \bmod 10 = \textcolor{red}{1}$	$15 \bmod 2 = 1$
$11\textcolor{red}{11} \bmod 100 = \textcolor{red}{11}$	$15 \bmod 4 = 3$

通过观察可以发现，在 $a$ 进制下，$m \bmod a^{k}$ 就是截断了前面的数在 $a$ 进制下的低 $\textcolor{red}{k}$ 位。

在二进制中怎么截断一个数呢？

需要哪几位，就 &(与) 一个哪几位全 1，其他位全 0 的数。

例如:

1	0111_1001 & 0000_1111 = 0000_1001

上面说需要截断低 $k$ 位，那就是 0000_k个1

又：0000_k个1 = 0001_k个0 - 1 = (1 << k) - 1 = 2^k - 1

所以 m & (2^k - 1) 即为截断取得 $m$ 后 $k$ 位

即 m % 2^k = m & (2^k - 1)

令 n = 2^k，则

m % n = m & (n - 1)

可得出结论，当 n 为 2 的幂的时候 m % n = m & (n - 1) = (n - 1) & m

转到 HashMap

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * Returns a power of two size for the given target capacity.
 *
 * 通过这个操作，保证 size 一定是 2 的幂
 */
static final int tableSizeFor(int cap) {
    // cap - 1 是为了防止 cap 本来就是 2 的幂 导致的容量翻倍
    int n = cap - 1;
    // 下面的操作是为了让 cap 的最高位变 0，后面的低位全部为 1
    // 最后当 n + 1 的时候，cap 最高位变 1 ，后面低位全部变 0，即 n + 1 为 2 的幂

    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

MUST be a power of two

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                  boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       
       // 这里的 (n - 1) & hash = hash % n
       // 因为 n 是 2 的幂
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
       else {
           ...
       }

tab[i = (n - 1) & hash] 就是在做 tab[hash % n] 这个操作

n 就是上面 MUST be a power of two 的值，所以 hash % n 的操作可以被优化为 (n - 1) & hash

位操作比除，取余的操作需要的时钟周期要少的多。

通过上面，只是可以知道这种优化方式，但仍不知是因为可以这么优化才设定 n 为 2 的幂，还是因为其他的因素设定 n 为 2 的幂，然后又可以采用这种优化，历史的事情，不好说。

java.time.chrono.IsoChronology#isLeapYear

/**
 * 判断闰年
 */
public boolean isLeapYear(long prolepticYear) {
    return ((prolepticYear & 3) == 0) && ((prolepticYear % 100) != 0 || (prolepticYear % 400) == 0);
}

里面的 (prolepticYear & 3) = (prolepticYear & (4 - 1)) = prolepticYear % 4

与操作奇偶数

n & 1 检查 n 的最后一位是不是 0 从而确定 n 是偶数还是奇数t

换一种思路 n % 2 = n & (2 - 1) = n & 1 从这种方式一样能推出这个优化。

结论

$m \bmod a^{k}$ 就是 $m$ 在 $a$ 进制下的低 $k$ 位；
对于二进制 $n = 2^{k}$ 可推出 m % n = m &(n - 1)。