给定两个整数,被除数dividend和除数divisor(都是正数,且不超过int的范围) 。 将两数相除,要求不使用乘法、除法和 % 运算符。 得到商和余数。java
时间: 2023-06-23 09:09:54 浏览: 99
在Python中获取两数相除的商和余数方法
可以使用位运算来实现除法操作。具体地,我们给出以下的定理:
定理:对于任意正整数 a 和 b,可以写成以下的形式:
a = b×2^k + a1
其中 a1 < b 且 k 是非负整数。
证明:首先,我们可以使用移位运算(即将二进制数向左或向右移动 k 位)得到 a 除以 2^k 的结果,即 a >> k。接下来,我们只需要计算 a1 / b 的值即可。由于 a1 和 b 均小于 b×2^k,因此可以使用递归的方式计算 a1 / b 的值。
根据上述定理,我们可以得到以下的 Java 代码实现:
```java
public int divide(int dividend, int divisor) {
if (dividend == Integer.MIN_VALUE && divisor == -1) {
return Integer.MAX_VALUE;
}
boolean negative = (dividend ^ divisor) < 0;
long t = Math.abs((long) dividend);
long d = Math.abs((long) divisor);
int result = 0;
for (int i = 31; i >= 0; i--) {
if ((t >> i) >= d) {
result += 1 << i;
t -= d << i;
}
}
return negative ? -result : result;
}
```
上述代码中,我们首先特判了一种情况:当被除数是 Integer.MIN_VALUE 且除数是 -1 时,由于结果会超过 int 类型的取值范围,因此需要返回 Integer.MAX_VALUE。接下来,我们通过异或运算来判断被除数和除数是否异号,并使用 long 类型来避免溢出。最后,我们从高位到低位枚举被除数的二进制位,如果当前的被除数大于等于当前的除数×2^i,则将结果加上 2^i,并将被除数减去除数×2^i。
阅读全文