不使用'/'的分部

Question

任何人都可以告诉我一种有效的方法来执行除法操作而不使用'/'.我可以log(n)使用类似于二进制搜索的方法逐步计算整数值.

115/3 
57 * 3 > 115
28 * 3 < 115
47 * 3 > 115
.
.
.
38 * 3 is quotient value .....

但还有其他更有效的方法吗？

Answer 1

典型的方法是移位和减法.这与我们在学校学到的长分工作基本相似.最大的区别在于,在十进制除法中,您需要估计结果的下一个数字.在二进制文件中,这是微不足道的.下一个数字始终为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正好填补它.

Answer 2

选项:

• 根据您在小学阶段学到的长除法算法编码您自己的除法算法.
• 取分母的-1次幂,然后乘以分子
• 取分子和分母的日志,减去,然后将日志的基数提升到相同的幂

我不是特别喜欢这样的问题,因为我们基本上都在寻找愚蠢的技巧,但我们确实如此.

Answer 3

以下是不使用除法运算符来划分数字的Java代码.

private static int binaryDivide(int dividend, int divisor) {
    int current = 1;
    int denom = divisor;
    // This step is required to find the biggest current number which can be
    // divided with the number safely.
    while (denom <= dividend) {
        current <<= 1;
        denom <<= 1;
    }
    // Since we may have increased the denomitor more than dividend
    // thus we need to go back one shift, and same would apply for current.
    denom >>= 1;
    current >>= 1;
    int answer = 0;
    // Now deal with the smaller number.
    while (current != 0) {
        if (dividend >= denom) {
            dividend -= denom;
            answer |= current;
        }
        current >>= 1;
        denom >>= 1;
    }
    return answer;
}

Answer 4

使用基础高中数学的简单Python实现。分母就是负1的幂的数字。

def divide(a, b):
    return a * b ** -1