谁能告诉我一个有效的方法，在不使用'/'执行除法运算。我可以使用类似于折半查找的方法计算的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?

推荐答案

典型的方法是转移和减法。这基本上是$，因为我们在学校里学过类似长除法p $ ptty的。最大的区别是，在小数除法，你需要评估结果的一个数字。在二进制，这是微不足道的。下一个数字始终为0或1。如果（左移）除数为小于或等于当前的被除数值，减去它，并将结果的当前位为1，如果是的，那么结果的当前位是0，code是这样的：

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;
}

本作品pretty的多的时候，我们做长除法手工等。例如，让我们考虑5分之972。在十进制长除法，我们做这样的事情：

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

因此​​，我们的第一步是要弄清楚，这将是在结果的第一位。我们通过比较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.

让我们考虑一下，涉及到了code以上。我们首先左移除数，直到它比股息。我们然后反复移位它的权利，并为每个右移检查值是否小于我们的最终减去后得到的中间。如果是少了，我们再减去并填写 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.

有人问我为什么用 | = ，而不是 + = 在code。我希望这有助于解释为什么。虽然在这种情况下，它们产生相同的结果，我不认为增加每一位到现有的部分答案。相反，我认为它的答案是空的点，而或只是填充入。

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.