Given two integers dividend
and divisor
, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend
by divisor
.
The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8
and truncate(-2.7335) = -2
.
Example 1:
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.
Example 2:
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.
给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去(truncate)其小数部分,例如:truncate(8.345) = 8 以及 truncate(-2.7335) = -2
提示显示:
由于不能使用乘法、除法和取余运算,所以想到利用位运算。位运算可以实现乘法的作用,位运算结合减法可以实现除法和取余效果。
a = b * d + c
,其中,商d可以分解为2的若干次幂的和,余数c 小于被除数b,在这个前提下,我们在a的基础上,反复减去b,同时记录b被减地次数,当a<b时,结束循环。 完整代码:
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
# 异或操作,用于判断两者是否同号
int sign = (dividend > 0) ^ (divisor > 0) ? -1 : 1;
long m = labs(dividend), n = labs(divisor), res = 0;
while (m >= n){
long p = n, t = 1;
while (m >= (p << 1)){
p <<= 1;
t <<= 1;
}
res += t;
m -= p;
}
return sign * res;
}
};
违规方法:但是能OC
代码:
class Solution {
public:
int divide(int dividend, int divisor) {
if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
return int(long(dividend)/long(divisor));
}
};
https://www.cnblogs.com/grandyang/p/4431949.html