高效取余运算(n-1)&hash原理探讨

2019-12-15 16:05:10来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

高效取余运算(n-1)&hash原理探讨

JavaHashMap源码中用到的(n-1)&hash这样的运算,查找发现这是一种高效的求余数的办法,但其中的原理是什么呢为什么可以这么做呢?

先上结论:假设被除数是x,对于除数是2n的取余操作x%2n,都可以写成x&(2n-1),位运算效率高!

 

eg:259%8=259&7=3

259    100000011
7      000000111
259&7=011=3

 

网上对这个原因的解释都是模糊不清,下面是我对于这个等式为什么成立的一些理解。

就拿上面这个259%8进行举例。

259的二进制为1000000118的二进制为1000

假如对8进行取余,那么只需要留下最后4位,前面的都可以舍弃,为什么呢?

因为比8更高位的都来自于82次幂,所以高位的1都是可以整除8,可以直接舍弃。

这解释了为什么只有除数是2n才可以这样的操作,因为如果除数是9的话,高位不一定能整除9,无法舍弃所以不行。(其余2n除数也同理)

也解释了为什么位数不同也可以做&操作,因为比除数高的位都是可以舍弃的。

 

 

 

然后就是&操作了,直接&8的话是不行的,假设最后四位是1XXX,那么1XXX&1000=1000,很明显对8取余得到的结果不可能是8,余数应在0到除数减一之间,

所以我们需要对&7,让取余结果最大在0-7之间。

这就解释了为什么要&(2n-1)

那有些人会问了,那我就是要&8,不就是相当于对9取余吗?

9取余就违反了上面的:“只有除数是2n才可以这样的操作

以上是个人对这个取余原理的理解,欢迎讨论


原文链接:https://www.cnblogs.com/powerzzjcode/p/12046695.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:SpringMvc 跨域处理

下一篇:Your activation code could not be validated (error 1653219)