文章目录

题目题解代码

题目

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

题解

这是LeetCode上面的一道题，题目要求不让用乘除法，那么首先我们就可以想到用 被除数-除数，直到被除数小于除数为止。很不幸，提交的时候超时了。那么我们可以再想办法进行优化，我们可以一下子减2^n个余数，尽可能的最大，这样花费的时间就会减少了。不让用乘除我们可以用位运算，左移一位相当于乘2。再进行减法的过程中，我们最好将两个数都变成负数，这样可以避免边界问题。

代码

下面是AC的代码

class Solution { public int divide(int dividend, int divisor) { if (dividend == -Integer.MAX_VALUE-1 && divisor == -1) return Integer.MAX_VALUE; int result = 0; boolean judgement = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0); //判断两数是否同号 //将被除数和除数都转化为负数 dividend = -Math.abs(dividend); divisor = -Math.abs(divisor); while (dividend <= divisor) { int t = divisor; int carry = 1; while (dividend - t < t) { t <<= 1; carry <<= 1; } dividend -= t; result += carry; } return judgement ? result : -result; } }