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

文章目录

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

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

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

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

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

y=a120+a221+...+an2n1+an+12n+an+22n+1+...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=120+021+022+123+124+025+...+02n1+02n+...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} + ...

其中a1=1a_1=1a2=0a_2= 0a3=0a_3=0a4=1a_4=1a5=1a_5=1a5a_5之后的都为0,这里面为了方便理解,把a5a_5之后都写出来了。

那么 y  %  xy\;\%\;x可以转换成:

y  %  x=(a120+a221+...+an2n1+an+12n+an+22n+1+...)  %  xy\;\%\;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=2nx=2^n,那么上面表达式可以转换为:

y  %  x=(a120+a221+...+an2n1+an+12n+an+22n+1+...)  %  2ny\;\%\;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=((a120+a221+...+an2n1)+(an+12n+an+22n+1+...))  %  2ny\;\%\;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分为从a1a_1ana_n和从an+1a_{n+1}到无穷这两部分,按照模运算规则:(a+b)  %  p=(a  %  p+b  %  p)(a + b) \;\%\; p = (a \;\%\; p + b \;\%\; p) % p,上面表达式可以继续转换成如下:

y  %  x=((a120+a221+...+an2n1)%2n+(an+12n+an+22n+1+...)%2n)  %  2ny\;\%\;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

由于(an+12n+an+22n+1+...)(a_{n+1} * 2^n + a_{n+2} * 2^{n+1}+...)可以整除2n2^n,上面表达式可以进一步简化为:

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

a120+a221+...+an2n1a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1}可能的最大值为2n12^n-1(当且仅当a1=a2=...=an=1a_1 = a_2 = ... = a_n = 1时),也就是说a120+a221+...+an2n1<2na_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} < 2^n, 那么存在:

(a120+a221+...+an2n1)%2n=a120+a221+...+an2n1(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=((a120+a221+...+an2n1)%2n)  %  2ny\;\%\;x= ((a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1})\%2^n)\;\%\;2^n进一步可以简化为:

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

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

a120+a221+...+an2n1=y  &  (20+21+...+2n1)a_1 * 2^0 + a_2 * 2^1 + ... + a_n * 2^{n-1} = y\;\&\;(2^0+2^1 + ... + 2^{n-1})

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

y  %  x=y  &  (20+21+...+2n1)=y  &  (2n1)=y&(x1)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  &  (x1)y\;\%\;x = y \;\&\; (x-1) 表达式是成立的。