y % x = y & (x - 1)的数学证明

文章目录

在基于哈希表实现的Map中一个常用技巧就是将哈希桶的数量设置为2的n次方，也就是$2^n$，此后通过取余操作定位key所在桶的位置可以转换成与运算。之所以将取余运算改成与运算，一方面这两者计算的结果是一样的，另外一方面是因为与运算具有更好的性能，因为与运算指令周期是小于取余运算的。Java中的 HashMap 和Go中 map 都使用到这个技巧。

基于哈希表实现的Map中的取余运算转换成与运算的技巧，用数学语言来表达：

对于正整数x, y，如果x为2的n次方，n为正整数，那么$y\;\%\;x = y \;\&\; (x-1)$ 表达式是成立的。

对于$y\;\%\;x = y \;\&\; (x-1)$等式的成立有很多理解角度，本文从数学角度出发，尝试以数学证明方式来证明它。证明过程如下：

y为正整数，将y转换成二进制后，其十进制的值可以用如下表达式表示，其中$a_1$，$a_2$，… $a_n$分别表示y二进制表示时其第1位，第2位，第n位上的值，依次类推：

$y = a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} + a_{n+1} * 2^n + a_{n+2} * 2^{n+1} +...$

举例说明，比如y为25时候，其对应二进制为11001，那么上面表达式表示如下：

$25 = 1 * 2^0 + 0 * 2^1 + 0 * 2^2 + 1 * 2^3 + 1 * 2^4 + 0 * 2^5 + ... + 0 * 2^{n-1} + 0 * 2^{n} + ...$

其中$a_1=1$，$a_2= 0$，$a_3=0$，$a_4=1$，$a_5=1$，$a_5$之后的都为0，这里面为了方便理解，把$a_5$之后都写出来了。

那么 $y\;\%\;x$可以转换成：

$y\;\%\;x= (a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} + a_{n+1} * 2^n + a_{n+2} * 2^{n+1} +...) \;\%\;x$

由于x是2的n次方，所以$x=2^n$，那么上面表达式可以转换为：

$y\;\%\;x= (a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} + a_{n+1} * 2^n + a_{n+2} * 2^{n+1} +...) \;\%\;2^n$

进一步转换成：

$y\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}) + (a_{n+1} * 2^n + a_{n+2} * 2^{n+1} +...))\;\%\;2^n$

从上面可以看到我们把y分为从$a_1$到$a_n$和从$a_{n+1}$到无穷这两部分，按照模运算规则：$(a + b) \;\%\; p = (a \;\%\; p + b \;\%\; p)$，上面表达式可以继续转换成如下：

$y\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n + (a_{n+1} * 2^n + a_{n+2} * 2^{n+1}+...)\%2^n)\;\%\;2^n$

由于$(a_{n+1} * 2^n + a_{n+2} * 2^{n+1}+...)$可以整除$2^n$，上面表达式可以进一步简化为：

$y\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n)\;\%\;2^n$

而$a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}$可能的最大值为$2^n-1$(当且仅当$a_1 = a_2 = ... = a_n = 1$时），也就是说$a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} < 2^n$, 那么存在：

$(a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n = a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}$

那么等式$y\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n)\;\%\;2^n$进一步可以简化为：

$y\;\%\;x= a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}$

上面等式中$a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}$的含义是y二进制表示时候第1位到n位，其对应的十进制整数结果可以用与运算$ y;&;(2⁰⁺²1 + … + 2^{n-1})$得到，存在以下等式：

$a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} = y\;\&\;(2^0+2^1 + ... + 2^{n-1})$

$y\;\%\;x= a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}$等式可以进一步简化处理得到我们要证明的等式：

$y\;\%\;x= y\;\&\;(2^0+2^1 + ... + 2^{n-1}) = y\;\&\;(2^n -1) = y \& (x -1)$

综上所述，对于正整数x, y，如果x为2的n次方，n为正整数，那么$y\;\%\;x = y \;\&\; (x-1)$ 表达式是成立的。