LRUCache原理

roundUpToPowerOfTwo(int i)

获取大于等于 某个整数 并且是 2 的幂数的整数

publicstaticintroundUpToPowerOfTwo(inti) {  i--;// If input is a power of two, shift its high-order bit right.// "Smear" the high-order bit all the way to the right.i |= i >>>1;  i |= i >>>2;  i |= i >>>4;  i |= i >>>8;  i |= i >>>16;returni +1;}

可以看到这个算法进行了 5 次移位操作，乍一看，一脸懵逼，这是在干嘛？

细细一想啊，我现在要获取一个是 2 的幂数的整数，那其二进制的表现形式就是其最高位为1 ，低位全部为 0；或者其低位全部为 1，只需再对其加 1，即可变成 2 的倍数。

举个例子：

1000 0000

0100 0000 // 无符号右移一位

1100 0000 // 上面两个执行或操作的结果

1100 0000

0011 0000 // 无符号右移二位

1111 0000 // 上面两个执行或操作的结果

1111 0000

0000 1111 // 无符号右移三位

1111 1111 // 上面两个执行或操作的结果

其实我们只需将我们的关注点放置其元素为1的最高位上，执行右移操作，紧接着是或操作，最后的结果就是将高位的1，向后涂抹 （smear），全部变为1。

移位5次的原因在于 Java 中的整数是32位的，正好是2的 5次方。

算法刚开始的减一操作，则是为了防止刚开始传入的数字便是 2 的幂数。用来保证最终的结果是大于等于传入的参数的值。