给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。

注意：

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

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

示例 1：

输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

输入：a = 0, b = 1
输出：0

示例 4：

输入：a = 1, b = 1
输出：1

 提示:

  • -231 <= a, b <= 231 - 1

  • b != 0

思路

  • 俄罗斯农民算法(移位相加法)+倍数相减法

  • 二分搜索(参考答案)

首先这种不能使用xxx方法的题目，一般机试时是不会出的，因为限制不了编辑器，人工阅卷又需要耽误时间。

但正因为不会出现在机试中，所以在手撕算法时却会成为热门，所以请不要违背题意的直接使用乘、除提交题目。

拿示例一来说，一个最直观的方法就是循环使用a-b，计算减了多少次，即可得到结果。

但请注意a、b的取值范围，如果a为2 ^ 31−1，b为1那么仅一次就需要计算2 ^ 31−1次，所以这个思路是不可行的。

那么，既然不能从被除数上下手，能否通过除数进行操作呢？如果大家对二分搜索熟悉，相信很快能找到思路。

初始化返回值ret = 0

如果被除数大于除数，则除数扩大一倍

若被除数仍大于除数，这除数再次扩大一倍

直到除数下一次翻倍比被除数大时，将被除数减去除数，并将ret+=除数扩大的倍数，结束这一轮循环

重复2、3、4，直到被除数小于除数，终止循环并返回ret即可。

另外：在计算开始时，我们需要注意判断除数和被除数的正负号问题。如果是Python，只需要记录正负号即可。但对于Java而言，

由于负数的取值比正数大1，转换成正数计算会造成溢出，所以简单的方式是将数字转化为负数来进行比较。

作者：清风Python

链接：https://leetcode.cn/problems/xoh6Oh/solutions/940024/shua-chuan-jian-zhi-offer-day01-zheng-sh-8u0s/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

  • 俄罗斯农民算法(移位相加法)+倍数相减法

class Solution {
    public int divide(int a, int b) {
        boolean flag = (a < 0) ^ (b < 0);
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            } else if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        if (a > 0) {
            a = -a;
        }
        if (b > 0) {
            b = -b;
        }
        if (a > b) {
            return 0;
        }
        int mid = 1;
        int temp = 1;
        while (temp > 0) {
            int product = shiftAdd(mid, b);
            if (product == a) {
                return flag ? -mid : mid;
            } else if (a - product <= product) {
                temp = mid;
                mid <<= 1;
            } else if (a - product <= shiftAdd(temp, b)) {
                mid += temp;
                temp >>= 1;
            } else {
                temp >>= 1;
            }
        }
        return flag ? -mid : mid;
    }

    private int shiftAdd(int a, int b) {
        int result = 0;
        while (a > 0) {
            if ((a & 1) == 1) {
                result += b;
            }
            a >>= 1;
            b <<= 1;
        }
        return result;
    }
}

  • 二分搜索

class Solution {
    public int divide(int a, int b) {
        boolean flag = (a < 0) ^ (b < 0);
        if (a > 0) {
            a = -a;
        }
        if (b > 0) {
            b = -b;
        }
        int ret = calc(a, b);
        if (!flag && ret == Integer.MIN_VALUE) {
            ret++;
        }
        return flag ? ret : -ret;
    }

    private int calc(int a, int b) {
        int ret = 0;
        while (a <= b) {
            int cnt = 1;
            int val = b;
            while (val >= Integer.MIN_VALUE >> 1  && a <= val << 1) {
                cnt += cnt;
                val += val;
            }
            ret -= cnt;
            a -= val;
        }
        return ret;
    }
}