【Java】使用位运算(&)代替取模运算(%)

栏目: Java · 发布时间: 6年前

内容简介:位运算(&)效率要比取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。来源自这个方法是使用哈希值对链表数组的长度取模,得到值所在的索引位置,里面使用位运算(&)代替普通的(%)运算。

位运算(&)效率要比取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。

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。

https://mp.weixin.qq.com/s?__biz=MzI3NzE0NjcwMg==&mid=2650120877&idx=1&sn=401bb7094d41918f1a6e142b6c66aaac&chksm=f36bbf8cc41c369aa44c319942b06ca0f119758b22e410e8f705ba56b9ac6d4042fe686dbed4&mpshare=1&scene=1&srcid=1010L0NNyoRB5lVoryo00awY#rd


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Programming Rust

Programming Rust

Jim Blandy / O'Reilly Media / 2016-8-25 / GBP 47.99

This practical book introduces systems programmers to Rust, the new and cutting-edge language that’s still in the experimental/lab stage. You’ll learn how Rust offers the rare and valuable combination......一起来看看 《Programming Rust》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

html转js在线工具
html转js在线工具

html转js在线工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具