倍增乘法(快速乘法)

所谓倍增乘法，简单理解就是每次用被除数减去[除数的最大的2x]，这样可以极大地增加处理的速度。

 /**     * 两数相除     *     * @param dividend 被除数     * @param divisor 除数     * @return 商（不包含小数）     */    public static int divide(int dividend, int divisor) {        long result = 0;        long x = dividend;        long y = divisor;        boolean negative = (x < 0 && y > 0) || (x > 0 && y < 0);        if (x < 0) {            x = -x;        }        if (y < 0) {            y = -y;        }        // 由于x/y的结果肯定在[0,x]范围内，所以对x使用二分法        long left = 0;        long right = x;        while (left < right) {            long mid = left + right + 1 >> 1;            if (quickMulti(mid, y) <= x) {                // 相乘结果不大于x，左指针右移                left = mid;            } else {                right = mid - 1;            }        }        result = negative ? -left : left;        // 判断是否溢出        if (result < Integer.MIN_VALUE || result > Integer.MAX_VALUE) {            return Integer.MAX_VALUE;        }                return (int)result;    } /**     * 快速乘法     *     * @param a 乘数     * @param b 被乘数     * @return 积     */    public static long quickMulti(long a, long b) {        long result = 0;        while (b > 0) {            if ((b & 1) == 1) {                // 当前最低位为1，结果里加上a                result += a;            }            // 被乘数右移1位，相当于除以2            b >>= 1;            // 乘数倍增，相当于乘以2            a += a;        }        return result;    }

34 在排序数组中寻找第一个和最后一个位置

  public int[] searchRange(int[] nums, int target) {   int[] res = new int[] {-1,-1};   int n = nums.length;            if(n==0) return  res;            if(n==1) {                if(nums[0]==target) return new int[]{0,0};                else return res;            }   int l =0,r=n-1;   int mid;   while(l<r) {   mid = l+r>>1;   if(nums[mid]>=target) {   r = mid;   }else {   l = mid+1;   }   }   if(nums[l]==target) {   res[0] = l;   }   while(l<n&&nums[l]==target) {   res[1] = l;                  l++;   }   return res;    }