关于二分时最容易出现的溢出问题
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的巧合，高位数据是被截断的，没有保存)，解决办法是选用更大的数据类型来处理乘法溢出问题。
腾讯云开发者
