文章目录

源码

 /** * Returns an {@code int} value with at most a single one-bit, in the * position of the highest-order ("leftmost") one-bit in the specified * {@code int} value. Returns zero if the specified value has no * one-bits in its two's complement binary representation, that is, if it * is equal to zero. * * @param i the value whose highest one bit is to be computed * @return an {@code int} value with a single one-bit, in the position * of the highest-order one-bit in the specified value, or zero if * the specified value is itself equal to zero. * @since 1.5 */
    public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

作用

<mark>把整数（4字节、32位）在二进制中除了最左边的1以外的1转换成0</mark>
例如：

代码分析

    public static int highestOneBit(int i) {
    //prat1：把最左边的1的右边全部转换成1 
    （目的：方便part2的实现）
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
	//part2：把最左边的1的右边全部转换成0
        return i - (i >>> 1);
    }

Part1:把最左边的1的右边全部转换成1

（目的：方便part2的实现）
<mstyle mathcolor="&#35;ff0011"> 假 如 传 入 </mstyle> \color{ff0011}{假如传入} 假如传入：0000 1*** **** **** **** **** **** ****
<mark>* 号表示任何数( 0 or 1 )。我不关心是什么，因为是0是1不影响</mark>
第一段代码：

 i |= (i >>  1);

翻译：(i >> 1);左移一位，然后与原数或运算 i |= (i >> 1)

e.g.

第二段代码：

 i |= (i >>  2);

e.g.

第三段代码：

 i |= (i >>  4);

e.g.

第四段代码：

 i |= (i >>  8);

e.g.

第五段代码：

 i |= (i >>  16);

e.g.

<mstyle mathcolor="&#35;ff0011"> p a r t 1 传 出 </mstyle> \color{ff0011}{part1传出} part1传出：0000 1111 1111 1111 1111 1111 1111 1111

Part2：把最左边的1的右边全部转换成0

<mstyle mathcolor="&#35;ff0011"> p a r t 1 传 出 的 i </mstyle> \color{ff0011}{part1传出的i} part1传出的i：0000 1111 1111 1111 1111 1111 1111 1111
作为Part2的输入

 return i - (i >>> 1);

<mark> <mstyle mathcolor="&#35;ff0011"> 最 终 输 出 </mstyle> \color{ff0011}{最终输出} 最终输出：0000 1000 0000 0000 0000 0000 0000 0000</mark>

应用

1. 找小于等于n的2的幂次数

System.out.println(Integer.highestOneBit(10)); 
System.out.println(Integer.highestOneBit(16));
System.out.println(Integer.highestOneBit(20));

2. <mark>找大于等于n的2的幂次数</mark>

		System.out.println(Integer.highestOneBit((10-1)<<1));
		System.out.println(Integer.highestOneBit((16-1)<<1));
		System.out.println(Integer.highestOneBit((20-1)<<1));

说明：

  1. 向左位移 ，目的：<mark>最左边1左移一位，如果原来不是2的幂，就能找到大于它的2的幂</mark>
  2. -1 ， 目的：<mark>保证，如果原来是2的幂，也能找到</mark>

例子 （HashMap扩容用到 - java1.7前）

HashMap.roundUpToPowerOf2() - java1.7

 private static int roundUpToPowerOf2(int number) {
        // assert number >= 0 : "number must be non-negative";
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
    }

总结

这代码写的真牛逼