侧边栏壁纸
博主头像
Wyatt博主等级

Done is better than perfect!

  • 累计撰写 103 篇文章
  • 累计创建 31 个标签
  • 累计收到 7 条评论

JDK 位运算(&)代替取模运算(%)

Wyatt
2020-10-17 / 0 评论 / 0 点赞 / 259 阅读 / 628 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2020-12-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

一. 简介

个人学习算法过程中,遇到的一个小知识点,特此记录。JDK中的哈希函数并没有直接采用取模运算,而是利用了位运算的方式来优化性能。
位运算(&)效率要比取模运算(%)高很多,因为位运算直接对内存数据进行操作,无需十进制转换,所以处理速度非常快。

a % b == a & (b - 1)

二. 原理

2.1 公式

X % 2n = X & (2n - 1)

2.2 解释

2n代表2的n次方,一个数对于2n取模也就等于它与(2^n-1)做按位与运算。

2.3 举例

当n为4时,24=16,则二进制为10000。右侧,此时24-1=15,它当二进制为01111.
当X &(2^4 - 1)= X的二进制的后三位。
所以,借助二进制 X / 8 == X>>3,此时得到了X / 8的商,而被移掉的部分(后三位),则是 X % 8,也就是余数。

2.4 进阶

对于所有 2^n 的数,二进制表示为:

100…000,1 后面跟 n 个 0

而 2^n - 1 的二进制为:

011…111,0 后面跟 n 个 1

综上,X / 2n 是 X >> n,那么 X & (2n - 1) 就是取被移掉的后 n 位,也就是 X % 2^n。

三. 结论

此道理虽然是很基础很简单,但是却是构建优质代码的基础。网上这个讲解很多,但是打牢基础很重要,温故而知新。加油。

0

评论区