public int rank(int key, int n) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + ((hi - lo) >> 1); //>>1是除以2 也可以直接(lo + hi) >>> 1
// 为什么不直接(lo+hi)>>1呢,因为lo+hi可能溢出,而hi-lo不溢出,lo+(hi-lo)>>1是小于hi的,也不溢出,更安全
int cmp = key - a[mid];// a为有序数组
if (cmp < 0) {
hi = mid - 1;
} else if (cmp > 0) {
lo = mid + 1;
} else {
return mid;
}
}
return lo;
}
我在上面的mid处理方法就是用的
int mid = lo + ((hi - lo) >> 1); 这种方法不限于语言,是各种编程语言通用的防溢出写法
在java中有 >>> 运算符
我发现Arrays.binarySearch()方法在处理mid时
int mid = (low + high) >>> 1;
Java中的位运算符:
>>表示算术右移,如果该数为正,则高位补0,若为负数,则高位补1;
>>>表示逻辑右移,也称为无符号右移,即若该数为正,则高位补0,而若该数为负数,则右移后高位同样补0。
很少有人知道<<在java中表示的是循环左移,即便是百度搜到的其他博客都没记载<<是循环左移。作为个人知识分享福利送给来看我博客还有耐心看完的朋友。
简单介绍循环左移:
举例1<<31 = -2147483648,1<<32=1等同于1 << 0,最高位符号位的1移动到了最低位。
1<<63 = -2147483648,1<<64=1。
1L<<63 = -9223372036854775808,1L<<64 = 1(long型的1)
所以在位图算法中,假设是long型数组
word[bitIndex << 6] |= 1L << (bitIndex % 64)
word[bitIndex << 6] |= 1L << (bitIndex & 63)等此类计算
计算偏移量没必要bitiIndex%64或者bitIndex & 63 ,直接(1L << bitIndex) 即可,移位比与或位运算更快。源码总结,不喜勿喷。
<<是循环移动所以可以移动负数个bit位,比如1<<-1=-2147483648等同于1<<31
而>>和>>>都不是循环移动,所以不能移动负数位,只要移动负数位,结果都为0,比如3>>-1=0,4>>>-1=0。
讲多了,言归正传,下面来看看>>>
比如int范围 -2147483648~2147483647
21亿多吧,如果在输入的时候超过int范围,编译器会报错,很明显就会知道自己错了。可是关键是输入的每个数字都很大,且没有超过int范围,但相加或者相乘操作超出了范围!!!这种情况很难查出来,会造成不必要的麻烦
>>>1操作非常好,举个例子
分别进行如下操作:
System.out.println(1500000000 + 1500000000);
System.out.println((1500000000 + 1500000000) >> 1);
System.out.println((1500000000 + 1500000000) >>> 1);
显示
-1294967296 (150000000 + 1500000000 (15亿加15亿))
10110010110100000101111000000000
-647483648 (>>1的情况)
11011001011010000010111100000000
1500000000 (>>>1的情况)
01011001011010000010111100000000 (正好就是相加除以2,也就是无符号右移一位)
再来一组例子
分别进行如下操作
System.out.println(1500000000 + 1200000000); // 15亿加12亿
System.out.println((1500000000 + 1200000000) >> 1);
System.out.println((1500000000 + 1200000000) >>> 1);
显示
-1594967296
10100000111011101011101100000000
-797483648 (>>1之后)
11010000011101110101110110000000
1350000000 (>>>1之后)
01010000011101110101110110000000 (正好就是相加除以2,也就是无符号右移一位)
综上所述,>>>1更安全,不会因为加法溢出而对结果产生影响。
但是>>>1只能解决加法溢出的问题,几乎是解决不了乘法溢出的问题(除非有类似乘以2再>>>1的巧合,高位数据是被截断的,没有保存),解决办法是选用更大的数据类型来处理乘法溢出问题。