“算”了么（一）

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

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

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

示例 1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。

来源：力扣（LeetCode）

审题：

1、暴力解法：

用除数一直减被除数，直到除数小于被除数

2、位运算：

左移：按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。

右移（带符号的）：按二进制形式把所有的数字向右移动对应的位数，低位移出(舍弃)，高位的空位补符号位，即正数补零，负数补1。

左移 === 在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次，左移n位就相当于乘以2的n次方。
右移 === 右移一位相当于除2，右移n位相当于除以2的n次方。这里是取商哈，余数就不要了。

位运算实现：

class Solution {
    public int divide(int dividend, int divisor) {
        //考虑特殊情况
        if(divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)){
            return Integer.MAX_VALUE;
        }
        //异或运算（找出符号）
        int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
        long ms = (long)dividend;
        long ns = (long)divisor;
        ms = Math.abs(ms);
        ns = Math.abs(ns);
        int num = 0;
        while(ms >= ns){
            long m = ns;
            long n = 1;
            while(ms >= (m << 1)){
                m <<= 1;
                n <<= 1;
            }
            num += n;
            ms -= m;
        }
        return num * sign;
    }
}

暴力法实现：

public int divide(int dividend, int divisor) {
        int sign = (dividend ^ divisor) >= 0 ? 1 : -1;//判断符号
        long dividendTemp = Math.abs((long) dividend);//求绝对值
        long divisorTemp = Math.abs((long) divisor);
        long res = 0;
        while (dividendTemp >= divisorTemp) {
            long tmp = divisorTemp;
            long times = 1;//除数divisor的倍数
            while (dividendTemp >= (tmp << 1)) {
                tmp <<= 1;
                times <<= 1;
            }
            //被除数减去除数的times倍
            dividendTemp -= tmp;
            //累加times
            res += times;
        }
        //添加符号
        res = sign > 0 ? res : -res;
        //需要判断是否有溢出
        return res > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) res;
    }

“算”了么 （一）

审题：

位运算实现：

暴力法实现：

“算”了么（一）