题目描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [$−2^{31}$, $2^{31}$ − 1]。本题中，如果除法结果溢出，则返回 $2^{31} − 1$。
题解
不能用乘除，那只能用加减？挨个减也太慢了，使用位运算显得比较合理。另外，$−2^{31}$取绝对值时需要单独处理，并且需要用到unsigned int。用异或来计算是否符号相异。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int divide(int dividend, int divisor) {
int min_limit = 0x80000000;
if (!dividend)return 0;
if (dividend == INT_MIN && divisor == -1)
return INT_MAX;
bool negative = (dividend^divisor) < 0;
unsigned int t = dividend == INT_MIN ? min_limit : abs(dividend);
unsigned int d = divisor == INT_MIN ? min_limit : abs(divisor);
unsigned int result = 0;
for (int i = 31; i >= 0; i--)
{
if (t >> i >= d)
{
result += ((unsigned int)1) << i ;
t -= d << i;
}
}
if (result == min_limit)
return INT_MIN;
return negative ? -(int)result : (int)result;
}
|