更高效的取余运算
平常的取余一般用%
运算符,在学习ArrayDeque
时发现其使用了另一种取余方法:
elements[head = (head - 1) & (elements.length - 1)] = e;
其中head
是该双向队列的头部下标,这段代码既可以解决下标为负的情况又可以起到取余的作用,其中(head - 1) & (elements.length - 1)
起到了对elements.length
取余的作用。
即a % b == a & (b-1)
,这个式子成立需要满足条件b == 2^n
,即a % b == a ^ (2^n - 1)
。
由于位运算是直接在内存中进行的,故比使用%
性能更好。