length = 2n 且X>0，X % length = X & (length - 1)

首先感谢由HashMap哈希算法引出的求余%和与运算&转换问题一文的思想，很厉害，看了好一会儿才看懂。
最近看ThreadLocal里面的ThreadLocalMap，取index的方式跟HashMap不太一样，但大致都是一个数与上length-1，就很奇怪，为什么一定要与上length-1。百思不得其解，于是看到了上面的文章，很有意思，文章里面有些地方还是有点小问题的，我按照我的思路再捋一遍。
左移右移忘记了的看这里，之前写的一些基础知识。
重复一遍结论：
length = 2ⁿ 且X>0，X % length = X & (length - 1) $\color{red}{公式一}$
这里我加了个条件X>0情况，因为在ArrayDeque的源码里面，计算存储范围的时候是(tail-head)&(length-1)，tail-head有可能是负的，这里我还没有搞清楚，有待后续研究。（想明白了，参考ArrayDeque源码分析最后面）。

正文开始

因为取余其实是一个十进制的操作，而与操作是二进制的操作，我们先看十进制二进制是怎么转化的：
一个n位的二进制数（X表示1或者0，n表示位数）左边二进制，右边十进制：
Xn-1Xn-2...X1X0 = X(n-1) * 2^n-1+...+X1 * 2¹ + X0 * 2⁰ $\color{red}{公式二}$
比如1010，n=4
So : 1010 = 1 * 2³ + 0 * 2² + 1 * 2¹ + 0 * 2⁰
这很好理解，开始验证：

左边 X % length

两个数字X和length和一个操作符 % ，我们在十进制的领域看这些操作：

X = X(n-1) * 2^n-1+...+X1 * 2¹ + X0 * 2⁰
length = 2^m (非常重要的条件)

怎么取余数呢？按照下面四步走：

X = 能除尽的部分 + 余数
能除尽的部分 = X(n-1) * 2^n-1+...+Xm * 2^m
余数 = X - 能除尽的部分
余数=X(m-1) * 2^m-1+...+X1 * 2¹ + X0 * 2⁰

得出结论length = 2^m的情况下X % length的结果是取X的后m位。是不是看着很眼熟了~~不熟也没关系，继续往下看：

右边 X & (length - 1)

两个数字X和length-1一个操作符&，我们在二进制的领域看这些操作：

X = Xn-1Xn-2...X1X0 （二进制，X为1或者0）
length - 1 (length = 2^m) => 10...00(m位) - 1 => 1...11(m-1位)

任何数跟0与操作都是0，任何数跟1与操作都是数字本身，所以：length - 1能看成0...00(x位)1...11(m-1位) 的组合，任何数跟它做与操作都只会剩下第位的m-1位。所以：
结果 = Xn-1Xn-2...X1X0 & 1...11(m-1位) => Xm-1...X1X0

对比两边结果

左边 = X(m-1) * 2^m-1+...+X1 * 2¹ + X0 * 2⁰
右边 = Xm-1...X1X0
我们看下上面的公式二：
Xn-1Xn-2...X1X0 = X(n-1) * 2^n-1+...+X1 * 2¹ + X0 * 2⁰ $\color{red}{公式二}$
把公式二的n换成m再看上面的左右结果，是不是很神奇。

上面说的是X是正数的情况，那如果是负数呢？
-10 % 16 = -10
-10 & 15 = 6
如果我们还是用来在一个HashMap做取index的操作，很明显我们需要的是&与操作。那为什么-10 & 15 = 6呢？这里我们不通过怎么取负数的二进制（负数的二进制要先取反码再取补码）来入手，我们从另外一个角度，我们知道 length & (length - 1) = 0，所以：
-10 & 15
= -10 & (16 - 1)
= (-10 + 16) & (16 - 1)
= 6 & (16 -1 )
= 6
同样能得到这个结论。

最后编辑于：2019.07.18 14:31:50