谁能告诉我不使用'/'来执行除法运算的有效方法。我可以使用类似于二进制搜索的方法以log(n)步骤计算整数值。
115/3
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....
但是还有其他更有效的方法吗？
最佳答案
典型的方法是移位和减去。这基本上类似于我们在学校学习的长除法。最大的区别是，在十进制除法中，您需要估计结果的下一位。用二进制表示，这很简单。下一个数字始终为0或1。如果(左移)除数小于或等于当前的被除数值，则将其减去，结果的当前位为1。如果大于，则结果的当前位为0。代码如下:
unsigned divide(unsigned dividend, unsigned divisor) {
unsigned denom=divisor;
unsigned current = 1;
unsigned answer=0;
if ( denom > dividend)
return 0;
if ( denom == dividend)
return 1;
while (denom <= dividend) {
denom <<= 1;
current <<= 1;
}
denom >>= 1;
current >>= 1;
while (current!=0) {
if ( dividend >= denom) {
dividend -= denom;
answer |= current;
}
current >>= 1;
denom >>= 1;
}
return answer;
}
这就像我们手工进行长除法一样。例如，让我们考虑972/5。在十进制长除法中，我们执行以下操作:
____
5)972
然后我们分别计算每个数字。 5一次变成9，因此我们在答案的那个数字中记下1，然后从被除数的(那个数)中减去1 * 5，然后“取下”被除数的下一位:
1
----
5)972
5
---
47
继续进行相同的操作，直到填写完所有数字为止:
194
----
5)972
5
---
47
45
---
22
20
---
2
因此，我们的答案是194余数2。
现在让我们考虑相同的东西，但是用二进制。二进制972是
11 1100 1100，5是101。现在，将二进制除以十进制和除以十进制之间存在一个根本区别:在十进制中，特定数字可能是0到9之间的任何数字，因此我们必须相乘才能找到要从被除数中减去的中间结果。在二进制中，数字永远只会是0或1。我们永远不需要乘法，因为我们只会乘以0或1(我们通常在if语句中处理-我们减去或不)。 -----------
101)1111001100
因此，我们的第一步是弄清楚哪个将是结果中的第一位。我们通过将101与1111001100进行比较，然后将其向左移动直到更大为止。这给了我们:
|
1111001100
10100000000
进行移位时，我们会计算已移位的位数，因此我们可以知道在任何给定时间要填充结果的哪几位。我已经在上方的垂直条上进行了展示。然后，我们将中间结果右移一位，并在其中将竖线右移，以表示我们要在哪里填充结果数字:
|
1111001100
1010000000
从那里，我们检查移位后的除数是否小于股息。如果是的话，我们在答案中的适当位置填写1，然后从中间结果中减去偏移的除数[并且为了保持列直，我将插入一些空格]:
1
-----------------------------
101)1 1 1 1 0 0 1 1 0 0
1 0 1 0 0 0 0 0 0 0
----------------------------
1 0 1
我们以相同的方式继续，填写结果的数字，然后从中间结果中减去移位的除数，直到填写完所有数字为止。为了进一步使事情变得简单，我将在结果的每一位写在被替代对象的最右边:
1 1 0 0 0 0 1 0
-----------------------------
101)1 1 1 1 0 0 1 1 0 0
1 0 1 1
-----------------------------
1 0 1
1 0 1 1
-----------------------------
0 0 0 0
--------------------------
0 0 0 0
-------------------------
0 0 1 0
-------------------------
0 1 1 0
-------------------------
1 1 0
1 0 1 1
------------------------
0 1 0 0
因此，我们得到11000010的结果，余数为10。将那些结果转换为十进制数，我们分别得到期望的194和2。
让我们考虑一下这与上面的代码之间的关系。我们首先将除数向左移动，直到除数大于被除数为止。然后，我们反复将其右移，并针对每个右移检查该值是否小于上次减法后得到的中间值。如果较小，我们再次减去并在结果中为该数字填写一个
1。如果更大，我们将“减去0”(不做任何事情)，并在结果中的那个数字上填一个“0”(同样，不需要我们做任何事情，因为这些数字已经设置为0)。当我们填写完所有数字后，这就是我们的结果，而我们尚未减去的剩余金额就是我们的余数。
有人问为什么我在代码中使用
|=而不是+=。我希望这有助于解释原因。尽管在这种情况下它们产生相同的结果，但我不认为要将每个数字添加到现有的部分答案中。相反，我认为答案中的那个位置是空的，而or只是填充了它。