给定两个整数,被除数dividend和除数divisor(都是正数,且不超过int的范围) 。 将两数相除,要求不使用乘法、除法和 % 运算符。 得到商和余数。
时间: 2023-09-10 10:05:15 浏览: 222
### 回答1:
这道题可以通过位运算来实现。我们可以先将被除数和除数都转换为正数,再一位一位地进行除法操作。具体步骤如下:
1. 将被除数和除数转换为正数,并记录下它们的符号。
2. 用被除数减去除数,直到被除数小于除数为止。每次相减后,将商的二进制表示左移一位,并将当前的差作为余数存入一个变量中。
3. 如果当前余数大于等于除数,则再用余数减去除数,并将商的二进制表示最低位设为1。
4. 重复步骤2和3,直到被除数小于除数为止。
5. 根据符号位决定商的正负性,并返回商和余数。
下面是实现代码:
```python
def divide(dividend: int, divisor: int) -> List[int]:
# 将被除数和除数都转换为正数,并记录下它们的符号
sign = 1 if (dividend > 0) == (divisor > 0) else -1
dividend, divisor = abs(dividend), abs(divisor)
# 特殊情况:除数为0或者被除数小于除数
if divisor == 0 or dividend < divisor:
return [0, dividend]
# 初始化商和余数
res, remainder = 0, 0
# 一位一位地进行除法操作
for i in range(31, -1, -1):
if remainder + (divisor << i) <= dividend:
remainder += divisor << i
res |= 1 << i
# 根据符号位决定商的正负性,并返回商和余数
return [sign * res, sign * (dividend - remainder)]
```
这个算法的时间复杂度是O(logN),其中N是被除数和除数的二进制表示的位数之和。
### 回答2:
可以通过位运算的方式实现两个整数的除法运算。具体步骤如下:
1. 首先判断被除数除以除数是否为0,如果是0,则无法进行除法运算,返回结果为0。
2. 判断被除数和除数的符号是否相同,如果不相同,则商的符号为负,否则商的符号为正。在后续计算中,将被除数和除数都转换为正数进行操作。
3. 使用循环,每次将被除数减去除数的2的n次方倍,其中n从0开始递增,并记录下来n的值。直到被除数小于除数为止。
4. 根据循环中记录的n的值,可以得到商的2的n次方倍值。将这个值转换为十进制数即为商。
5. 最后根据符号判断商的正负,并返回商和被除数剩余的值。
举个例子,假设被除数为15,除数为3:
1. 15和3的符号相同,商的符号为正。
2. 循环计算:15-3=12(2^0=1),12-6=6(2^1=2),6-6=0(2^2=4),循环结束。
3. 根据循环记录的n的值,得到商的2^0+2^1=3。
4. 返回商为3,被除数剩余的值为0。
需要注意的是,这种方法只适用于正数情况,对于负数的除法运算,可以先将两个整数都转换为正数进行操作,最后根据符号判断商的正负即可。
### 回答3:
题目要求我们计算两个正整数的除法结果,但是不能使用乘法、除法和取余运算符。那么我们可以采用位运算来解决这个问题。
首先,我们需要判断被除数是否大于除数,如果不大于则直接返回0。然后,我们定义两个变量div和num,初始值分别为被除数和除数。
接下来,我们利用二进制的特性来进行计算。先将除数左移一位(相当于乘2),与被除数比较。如果除数小于被除数,就将divisor加到num上,divisor再左移一位,即num=divisor*2。重复以上步骤,直到找到最大的一个num,使得num大于被除数,然后将divisor右移一位,即num=num>>1,同时将商res左移一位(相当于商乘2),并将被除数减去num,即div=div-num。
上述步骤重复执行,直到div等于0。最后,判断商的正负号,即被除数和除数的正负号是否相同。如果不相同,则结果取反。最后返回商和余数。
例如:被除数dividend=15,除数divisor=3。
初始化div=15, num=3, res=0。
经过循环找到最大的一个num=3*2=6,此时将divisor右移一位,num=num>>1=3,div=div-num=15-6=9,res=res<<1=0
再次执行循环,找到最大的一个num=3*2=6,此时将divisor右移一位,num=num>>1=3,div=div-num=9-6=3,res=res<<1+1=1
再次执行循环,找到最大的一个num=3*2=6,此时将divisor右移一位,num=num>>1=3,div=div-num=3-3=0,res=res<<1=2
最后返回商和余数,即商为2,余数为0。
这种方法时间复杂度为O(log(dividend/divisor)),因为除数每次右移一位,所以最多执行log次。
阅读全文