盒子
盒子
文章目录
  1. 29. 两数相除

29_两数相除_leetcode

29. 两数相除

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。

输入: dividend = 10, divisor = 3
输出: 3
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−2^31, 2^31 − 1]。本题中,如果除法结果溢出,则返回 2^31 − 1

题解:这题是除法,所以先普及下除法术语商,公式是:(被除数-余数)÷除数=商,记作:被除数÷除数=商…余数,是一种数学术语。在一个除法算式里,被除数、余数、除数和商的关系为:(被除数-余数)÷除数=商,记作:被除数÷除数=商…余数,进而推导得出:商×除数+余数=被除数。要求商,我们首先想到的是减法,能被减多少次,那么商就为多少,

但是明显减法的效率太低那么我们可以用位移法,因为计算机在做位移时效率特别高,向左移1相当于乘以2,向右位移1相当于除以2。我们可以把一个dividend(被除数)先除以2^n,n最初为31,不断减小n去试探,当某个n满足dividend/2^n>=divisor时,表示我们找到了一个足够大的数,这个数乘以divisor是不大于dividend的,所以我们就可以减去2^n个divisor,以此类推

我们可以以100/3为例2^n是1,2,4,8…2^31这种数,当n为31时,这个数特别大,100/2^n是一个很小的数,肯定是小于3的,所以循环下来,当n=5时,100/32=3, 刚好是大于等于3的,这时我们将100-32*3=4,也就是减去了32个3,接下来我们再处理4,同样手法可以再减去一个3,所以一共是减去了33个3,所以商就是33

这其中得处理一些特殊的数,比如divisor是不能为0的,Integer.MIN_VALUE和Integer.MAX_VALUE

题解来源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int divide(int dividend, int divisor) {
if (divisor == 0) {
return 0;
}
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative = (dividend ^ divisor) < 0; // 异或判断符号是否相等
long dividendAbs = Math.abs((long)dividend);
long divisorAbs = Math.abs((long)divisor);
int result = 0;
for (int i = 31; i >= 0; i--) {
if ((dividendAbs >> i ) >= divisorAbs) {
result += 1 << i;
dividendAbs -= divisorAbs << i;
}
}
return negative ? -result : result;
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫