不使用'/'的除法 [英] Division without using '/'
问题描述
谁能告诉我一种不使用/"来执行除法运算的有效方法.我可以使用类似于二进制搜索的方法在 log(n) 步骤中计算整数值.
Can anyone tell me an efficient approach to perform the division operation without using '/'. I can calculate the integer value in log(n) steps using a method similar to binary search.
115/3
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....
但是还有其他更有效的方法吗?
But is there any other more efficient method?
推荐答案
典型的做法是移位和减法.这基本上与我们在学校学到的长除法非常相似.最大的区别在于，在十进制除法中，您需要估计结果的下一位.在二进制中，这是微不足道的.下一个数字始终是 0 或 1.如果(左移)除数小于或等于当前被除数值，则将其减去，结果的当前位为 1.如果大于，则结果的当前位为 0.代码如下所示:
The typical way is to shift and subtract. This is basically pretty similar to long division as we learned it in school. The big difference is that in decimal division you need to estimate the next digit of the result. In binary, that's trivial. The next digit is always either 0 or 1. If the (left-shifted) divisor is less than or equal to the current dividend value, you subtract it, and the current bit of the result is a 1. If it's greater, then the current bit of the result is a 0. Code looks like this:
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.在十进制长除法中，我们这样做:
This works pretty much like when we do long division by hand. For example, let's consider 972/5. In decimal long division, we do something like this:
____
5)972
然后我们单独计算每个数字.5 进入 9 一次，所以我们在答案的那个数字上写一个 1，然后从被除数的(那个数字)中减去 1*5，然后减少"被除数的下一个数字:
Then we figure each digit individually. 5 goes into 9 once, so we write down a 1 in that digit of the answer, and subtract 1*5 from (that digit) of the dividend, then "bring down" the next digit of the dividend:
1
----
5)972
5
---
47
我们继续做同样的事情，直到我们填完所有的数字:
We continue doing the same until we've filled in all the digits:
194
----
5)972
5
---
47
45
---
22
20
---
2
所以，我们的答案是 194 余数 2.
So, our answer is 194 remainder 2.
现在让我们考虑同样的事情，但是是二进制的.二进制的972是11 1100 1100，5是101.现在，在二进制与十进制中进行除法之间存在一个根本区别:在十进制中，特定数字可以是 0 到 9 之间的任何数字，因此我们必须进行乘法才能找到要从被除数中减去的中间结果.在二进制中，数字只会是 0 或 1.我们永远不需要乘法，因为我们只会乘以 0 或 1(我们通常在 if 语句中处理——要么减，要么不减).
Now let's consider the same thing, but in binary. 972 in binary is 11 1100 1100, and 5 is 101. Now there is one fundamental difference between doing the division in binary vs. decimal: in decimal a particular digit could be anything from 0 to 9, so we had to multiply to find the intermediate result we were going to subtract from the dividend. In binary the digit is only ever going to be a 0 or a 1. We never need to multiply because we would only ever multiply by 0 or 1 (which we normally handle in an if statement--either we subtract or we don't).
-----------
101)1111001100
因此，我们的第一步是确定哪个将是结果中的第一个数字.为此，我们将 101 与 1111001100 进行比较，然后将其向左移动直到更大.这给了我们:
So, our first step is to figure out which will be the first digit in the result. We do that by comparing 101 to 1111001100, and shifting it left until it's greater. That gives us:
|
1111001100
10100000000
当我们进行移位时，我们会计算我们移位的位置数，以便我们知道在任何给定时间我们要填写的结果的哪一位.我已经用上面的垂直条显示了这一点.然后我们将中间结果向右移动一个位置，并将垂直条向右移动以表示我们正在做的填充结果数字的位置:
As we do that shifting, we count the number of places we've shifted so we know which digit of the result we're filling in at any given time. I've shown that with the vertical bar above. Then we shift the intermediate result right one place, and shift the vertical bar right with it to signify where we're doing to fill in a result digit:
|
1111001100
1010000000
从那里我们检查移动的除数是否小于被除数.如果是，我们在答案中的适当位置填入 1，然后从中间结果中减去移位的除数 [并帮助保持列直，我将插入一些空格]:
From there we check if the shifted divisor is less than the dividend. If it is, we fill in a 1 in the proper place in the answer, and subtract the shifted divisor from the intermediate result [and to help keep columns straight, I'm going to insert some spaces]:
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
我们继续相同的方式，填充结果的数字，并从中间结果中减去移位的除数，直到我们填充了所有数字.为了进一步尝试让事情变得简单，我将在最右边的减数旁边写下结果的每个数字:
We continue the same way, filling in digits of the result, and subtracting the shifted divisor from the intermediate result until we've filled in all the digits. In a further attempt at helping keep things straight, I'm going to write in each digit of the result at the far right next to the subtrahend:
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.
So, we get a result of 11000010, remainder 10. Converting those to decimal, we get the expected 194 and 2 respectively.
让我们考虑一下这与上面的代码有何关系.我们首先将除数向左移动，直到它大于被除数.然后我们反复将其右移，并为每次右移检查该值是否小于我们在最后一次减法后得到的中间值.如果小于，我们再次减去并在结果中为该数字填充 1.如果它更大，我们减去 0"(不做任何事情)并在结果中为该数字填充一个0"(这同样不需要我们做任何事情，因为这些数字已经设置为0.
Let's consider how that relates to the code above. We start by shifting the divisor left until it's greater than the dividend. We then repeatedly shift it right and for each right shift check whether that value is less than the intermediate we got after the last subtraction. If it's less, we subtract again and fill in a 1 for that digit in our result. If it's greater, we "subtract 0" (don't do anything) and fill in a '0' for that digit in the result (which, again, doesn't require us to do anything, since those digits are already set to 0's).
当我们填满所有数字后，这就是我们的结果，我们还没有减去的任何剩余金额就是我们的余数.
When we've filled in all the digits, that's our result, and any amount left that we haven't subtracted yet is our remainder.
有人问我为什么在代码中使用 |= 而不是 +=.我希望这有助于解释原因.尽管在这种情况下它们产生相同的结果，但我不考虑将每个数字添加到现有的部分答案中.相反，我认为答案中的那个位置是空的，而 or 只是将其填满.
Some have asked why I used |= instead of += in the code. I hope this helps explain why. Although in this case they produce the same result, I don't think of adding each digit to the existing partial answer. Rather, I think of it that spot in the answer as being empty, and the or just fills it in.
这篇关于不使用'/'的除法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
