leetocode 29. 两数相除-java

题目所属分类

二进制 也就是剑指Offer的第一题

概念小知识：
概念：首先解释一下左移右移，举例一个二进制数1000（十进制为8），此时的小数点在最右边，也就是：1000.

左移或者右移就是小数点不动，将数字整体左移或者右移，此时应该注意：
（1）如果是左移，低位（也就是靠近小数点的位）需要补0，左移几就补多少个0。

例如： 1000左移一位，写法是为 8 << 1, 那么二进制数就变为了10000，此时十进制值为16

（2）右移时，如果是正数，则高位补0，如果是复数，则高位补1.

另外，>>>表示无符号右移，不管是正数还是负数，都在移动之后在最高位补0.

如果使用>>>时，该数为正数，则和>>一样效果。

原题链接

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

代码案例：输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3

题解

y总解法的解析

参照别人写法的解析：
a>>>i 这是无符号右移 利用二进制 相当于 a/ (2^i)
(a >>> i) - b >= 0)这相当于a/b >= 2^i 也就是说a的第i位是1 然后a要减去
2^i 乘以b 结果就是res 加上
2^i
相反如果
a/b < 2^i 说明a的第i位是0

class Solution {
    public int divide(int x, int y) {
        if(x == Integer.MIN_VALUE && y == -1) return Integer.MAX_VALUE;
        int a  = Math.abs(x) ,b = Math.abs(y),res = 0; 
        for(int i = 31 ; i >= 0 ; i--){
                if((a >>> i) - b >= 0){
                    a -=  b << i;
                    res += 1 << i;
                }
        }
        return (x > 0) == (y > 0) ? res : -res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13