LeetCode

highestOneBit()算法解析

Posted by Tfly on 2019-07-10

Integer类有个highestOneBit()方法，作用是返回具有单个 1 位的 int 值, 在指定值中最高位的 1 位的位置，比如5(00000101)返回4(00000100)。

highestOneBit()的算法如下:

1
2
3
4
5
6
7
8
9
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);
}

为了书写简单，以一个字节为例，最高位表示符号位，以参数为5为例解释算法：

  1. 第一步:i |= (i >> 1)使i出现1的最高位至多连续2位都为1(包括最高位)
    0000 0101 >>1 = 0000 0010
    0000 0101 | 0000 0010 = 0000 0111
  2. 第二步：i |= (i >> 2),使i出现1的最高位的至多连续4位都为1(包括最高位)
    0000 0111 >>2 = 0000 0001
    0000 0111 | 0000 0001 =0000 0111
  3. 第三步:i |= (i >> 4)，使i出现1的最高位的至多连续8位都为1(包括最高位)
    0000 0111 >>4 =0000 0000
    0000 0111 | 0000 0000 =0000 0111
  4. 第四步：i - (i >>> 1)，减掉最高位后面的1
    0000 0111 >>>1 =0000 0011
    0000 0111 - 0000 0011 = 0000 0100

负数最高位为1。

FEATURED TAGS
LeetCode