【Java】使用位運算(&)代替取模運算(%)
位運算(&)效率要比取模運算(%)高很多，主要原因是位運算直接對記憶體資料進行操作，不需要轉成十進位制，因此處理速度非常快。
a % b == a & (b - 1)
前提：b 為 2^n
來源自HashMap
中的indexFor
方法：
static int indexFor(int h, int length){
return h & (length-1);
}
這個方法是使用雜湊值對連結串列陣列的長度取模，得到值所在的索引位置，裡面使用位運算（&）代替普通的（%）運算。
原理
具體的效率對比這裡不贅述，簡單說一下為什麼&
可以代替%
：
X % 2^n = X & (2^n - 1)
2^n 表示 2 的 n 次方，也就是說，一個數對 2^n 取模相當於一個數和 (2^n - 1) 做按位與運算 。
假設 n 為 3，則 2^3 = 8，表示成 2 進位制就是 1000。2^3 - 1 = 7 ，即 0111。
此時 X & (2^3 - 1) 就相當於取 X 的 2 進位制的最後三位數。
從 2 進位制角度來看，X / 8 相當於 X >> 3，即把 X 右移 3 位，此時得到了 X / 8 的商，而被移掉的部分(後三位)，則是 X % 8，也就是餘數。
推廣到一般：
對於所有 2^n 的數，二進位制表示為：
1000…000，1 後面跟 n 個 0
而 2^n - 1 的二進位制為：
0111…111，0 後面跟 n 個 1
X / 2^n 是 X >> n，那麼 X & (2^n - 1) 就是取被移掉的後 n 位，也就是 X % 2^n。
ofollow,noindex">https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650120877&idx=1&sn=401bb7094d41918f1a6e142b6c66aaac&chksm=f36bbf8cc41c369aa44c319942b06ca0f119758b22e410e8f705ba56b9ac6d4042fe686dbed4&mpshare=1&scene=1&srcid=1010L0NNyoRB5lVoryo00awY#rd