内容简介:位运算(&)效率要比取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。来源自这个方法是使用哈希值对链表数组的长度取模,得到值所在的索引位置,里面使用位运算(&)代替普通的(%)运算。
位运算(&)效率要比取模运算(%)高很多,主要原因是位运算直接对内存数据进行操作,不需要转成十进制,因此处理速度非常快。
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。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Hostens 储存型VPS代替网盘
- 使用dat代替resilio sync分享数据
- 培训出来的程序员容易被代替吗?
- es6 - let能代替var嘛
- redis 用scan指令 代替keys指令(详解)
- 可代替 ASM,使用 AnnotationProcessor 做代码插桩
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Android群英传
徐宜生 / 电子工业出版社 / 2015-9 / 69.00元
《Android群英传》对具有一定Android开发基础的读者,以通俗易懂的语言介绍了Android开发的进阶技巧。《Android群英传》共分为13章,讲解了Android体系与系统架构、Android开发工具新接触、Android控件架构与自定义控件详解、ListView使用技巧、Android Scroll分析、Android绘图机制与处理技巧、Android动画机制与使用技巧、Activi......一起来看看 《Android群英传》 这本书的介绍吧!