作者：曾雅芬珍念孟璇 | 来源：互联网 | 2023-05-19 05:38
最近本人在看jdk源代码的时候很有感触，感叹代码是如此的精炼。就好比说这个最容易被忽视的Integer。Integer是对int 类型的封装，这点大家都知道。今天我尝试来分析其部分本人认为比较有意思的源代码。
1 如何来找一个整数中其所对应的二进制数值中，最高位1所代表的数值。例如01000。代表的是8
public static int highestOneBit(int i) {
i |= (i >> 1);
i |= (i >> 2);
i |= (i >> 4);
i |= (i >> 8);
i |= (i >> 16);
return i - (i >>> 1);
}
代码解析:因为int类型是4个字节，也就是32位。当我们完成以上操作的时候，就能够保证最高位1后的低位数值全都位1。然后用i-(i>>>1)。这样就得到值了。注意这里一定要i>>>1。因为i有可能为负数。
2 如何来找一个整数中其所对应的二进制数值，最低位1所代表的数值。例如0101代表的值是2。
这里先说一下思路，假设这个二进制值是00111xxxxx。这个xxxxxx代表的是0或者没有。大多数人都知道负数的二进制码也就是补码是反码+1。补码&反码的值肯定为0。那和反码加1呢。这里分为两种情况。如果xxxx没有占用位数。也就是001111是最后的几位。那得到的是1。如果说xxxxx占用位数，那反码后得到的值也全都是1。然后加1。
所以代码非常简单。
public static int lowestOneBit(int i) {
return i & -i;
}
3 如何查找最高位1是第几位。 这里实现的思路是最高为1前面有几个0。然后用32-。 public static int numberOfLeadingZeros(int i) {
// Hacker's Delight, Figure 5-6
if (i <= 0) {
return (~i >> 26) & 32;
}
int n = 1;
if (i >> 16 == 0) {
n += 16;
i <<= 16;
}
if (i >> 24 == 0) {
n += 8;
i <<= 8;
}
if (i >> 28 == 0) {
n += 4;
i <<= 4;
}
if (i >> 30 == 0) {
n += 2;
i <<= 2;
}
return n - (i >>> 31);
}
代码解析：1 如果i为负数，则返回值为0。
2 如果是正数。总体的思路就是逐步的判断最高位1的位置。采用类似二分法。所采用的二分点在最高位1所可能在的区域。按照流程走一遍。
1 先把这个数值向右移动16位，如果说等于0。说明最高位1位于低16位数值。然后把这个值往左移动16位。
如果说大于0。说明这个最高位1位于高16位中的某一位。
按照这样的思路，我们就是在可能的区域中，然后取中间那个数，往右移动作比较。（对不起描述的不是很好）
这里要注意一点就是n初始值是为1的。就是假设经过以上步骤后，i>>>31得到的也为0。所以最终的值为:n-(i>>>31)
这里得到的数值是最高位1前面0的个数。
然后你32减所得到的值就是了。
4 给定一个数值a，找出一个比a大或者等于的最小的2的幂数值。比如说7的时候，找到值8.
实现代码如下:
public static int roundUpToPowerOfTwo(int i) {
i--;
i |= i >>> 1;
i |= i >>> 2;
i |= i >>> 4;
i |= i >>> 8;
i |= i >>> 16;
return i + 1;
}
减1的目的是防止i就是一个符合条件的数值。比如说8.分析的方法，跟前面一个样。
![[线段树|平衡树|树状数组]LightOJ - 1087 - Diablo](https://img1.php1.cn/3cd4a/24de0/243/98e55c73e9f2c673.jpeg)
京公网安备 11010802041100号