为什么在这个二进制除法案例中左移商？

Question

这是一个困扰我很久的问题。

考虑二进制数 0b10101（基数 10 中的 21）除以二进制数 0b10（基数 10 中的 2）。由于除以二是右移一，很明显商（截断）是 0b1010 ！我正在尝试在 C 中实现二进制除法但是最近，我尝试用笔和纸来做这个，并且很困惑地在途中被暂停了！

我的算法很简单，我通过适当的左移将除数的最高位与被除数对齐，然后进行比较以获得商的位，然后减去得到下一个被除数迭代。

我们继续这个欧几里德除法，直到我们得到红利 < 余数。

但是，考虑：

10 ) 10101 ( 101
    -10000 
     ------------
           101 
         -1000
     -------------
            101
           -100
     -------------
              1 // Why don't you stop here ? 
                       // Since at this step the dividend is less than divisor?

我知道我算法错误得到的上述商是错误的！商应为 0b1010 !

为什么我们要将商左移一位？
- 为什么我们在essence等待对齐的bits 除数 0b10000 等于位原始除数的数目 0b10，尽管已成功计算余数 ?

Answer 1

和小学一模一样...

   -------------
10 ) 10101

10 变成 1 多少次？零

     0
   -------------
10 ) 10101

进10？ 1 次

     01
   -------------
10 ) 10101
     10
    ----
      01

进入01多少次？零次

     010
   -------------
10 ) 10101
     10
    ----
      010

10进多少次？一次

     0101
   -------------
10 ) 10101
    -10
    ----
      010
      -10
      ------
        01

进入01多少次？零次

     01010
   -------------
10 ) 10101
    -10
    ----
      010
      -10
      ------
        01

答案：1010余1

最大的区别是在小学你有点需要记住乘法 table，对于二进制它是零次或一次，你基本上可以模式 match/greater 小于基于位而不是必须乘以某些东西。

编辑

小学，十进制

   -----------
10 ) 1234

     0
   -----------
10 ) 1234
     12

     01
   -----------
10 ) 1234
     12
    -10
    ---
      23

     012x
   -----------
10 ) 1234
     12
    -10
    ---
      23
     -20
     ------
       3

你是说在小学时你被教导到此为止，而不是填写分子以上的所有位置？你让 ones 列像那样悬空？空缺？为什么基数 2 会有所不同或基数 7 或基数 97？

我们被教导至少要完成所有的小数点，然后根据我们所在的学校的年份，我们继续完成但至少在这种情况下完成那些列然后你就可以停止对于整数数学。

10进34 3次

     0123
   -----------
10 ) 1234
     12
    -10
    ---
      23
     -20
     ------
       34 
      -30
     ------
        4

这个特殊的数学运算没有什么不同。

1234 / 10 是 123 而不是 12。

0b10101 / 0b10 是 0b1010 而不是 0b101

编辑 2

以编程方式比较容易做到

    ------------
abc ) defg...

累加器ra，分子rb，分母rc，结果rd

在小学时，我们被教导一次处理一个分子数字，累加器通过简单地在其右侧添加下一个数字然后再次用分母进行测试，将累加器左移一位，分子在那个时间点为累加器得到一个高于它的数字。因此，我们从一个空的累加器开始，每次迭代都将 ms 数字从分子中拉出，直到我们用完所有 digits/bits 而不是其中的大部分。所以第一个循环是 d 位，第二个是 e 位，第三个是 f 位，依此类推，直到我们用完整数分子中的数字。

ra = 0;
rd = 0
For number of bits in the numerator:
  ra<<=1; //make room for next bit from numerator
  ra|=(rb>>(nbits-1))&1;
  rb<<=1; //prep for next loop
  rd<<=1; //make room for next result bit, fill with zero
  if(ra>=rc) // <-base 2 optimization either it is a 0 or 1
  { 
      rd|=1; //result for this bit is a 1 not zero
      ra-=rc; //subtract one times denominator from accumulator
  }

按照这些思路，我已经验证了执行此操作的 C 代码。了解分子和分母的大小以及您想使用 32 位变量的其他变量的大小是有限制的，但要保持 numerator/denominator 的大小比 10101 和 10 小得多。

与小学数学 1234/10 相同

从0的累加器开始左移取第一个数字

1 / 10 = 0 remainder 1  (10^3 column 1)

余数是累加器所以取下一个数字 2 左移 1 并插入 2 得到 12

12 / 10 = 1 remainder 2 (10^2 column 2)

23 / 10 = 2 remainder 3 (10^1 column 3)

34 / 10 = 3 remainder 4 (19^0 column 4)

现在我们已经涵盖了从 10^n 到 10^0 的所有有效数字千位列到个位列，即整数结果。

因此，您可以通过编程方式将累加器移至下一位，将累加器与分母进行比较，确定基数的幂的结果，减去累加器，重复直到完成这些列，或者如果需要继续进行超越 decimal/binary 点。

编辑 3（固定）

如果你在做重复的减法

10101 - 10 = 10001  (1)
10011 - 10 = 10001  (2)
10001 - 10 = 1111  (3)
1111 - 10 = 1101  (4)
1101 - 10 = 1011  (5)
1011 - 10 = 1001  (6)
1001 - 10 = 111  (7)
111 - 10 = 101  (8)
101 - 10 = 11  (9)
11 - 10 = 1 (10)

是的，这令人困惑，股息可能需要为零或更少。我做的长除法总是有效的。

编辑 4

#include <stdio.h>
unsigned int fun ( unsigned int a, unsigned int b )
{
    unsigned int c;
    c = 0;
    while(a>b)
    {
       a-=b;
       c++;
    }
    return(c);
}
int main ( void )
{
    printf("%u\n",fun(21,2));
    return(0);
}

gcc so.c -o so
./so
10

编辑 5

#include <stdio.h>
unsigned int fun ( unsigned int a, unsigned int b )
{
    unsigned int c;
    c = 0;
    while(a>b)
    {
       a-=b;
       c++;
       printf("%u %u %u \n",a,b,c);
    }
    return(c);
}
int main ( void )
{
    printf("%u\n",fun(21,2));
    return(0);
}

19 2 1 
17 2 2 
15 2 3 
13 2 4 
11 2 5 
9 2 6 
7 2 7 
5 2 8 
3 2 9 
1 2 10 
10

#include <stdio.h>
unsigned int fun ( unsigned int a, unsigned int b )
{
    unsigned int c;
    c = 0;
    while(a>b)
    {
       printf("%u %u %u \n",a,b,c);
       a-=b;
       c++;
    }
    return(c);
}
int main ( void )
{
    printf("%u\n",fun(21,2));
    return(0);
}

21 2 0 
19 2 1 
17 2 2 
15 2 3 
13 2 4 
11 2 5 
9 2 6 
7 2 7 
5 2 8 
3 2 9 
10

#include <stdio.h>
unsigned int fun ( unsigned int a, unsigned int b )
{
    unsigned int c;
    c = 0;
    while(a>b)
    {
       printf("%u %u ",a,b);
       a-=b;
       c++;
       printf("%u \n",c);
    }
    return(c);
}
int main ( void )
{
    printf("%u\n",fun(21,2));
    return(0);
}

21 2 1 
19 2 2 
17 2 3 
15 2 4 
13 2 5 
11 2 6 
9 2 7 
7 2 8 
5 2 9 
3 2 10 
10

那是问题所在，修复了编辑 3。

10101 - 10 = 10001  (1)
10011 - 10 = 10001  (2)
10001 - 10 = 1111  (3)
1111 - 10 = 1101  (4)
1101 - 10 = 1011  (5)
1011 - 10 = 1001  (6)
1001 - 10 = 111  (7)
111 - 10 = 101  (8)
101 - 10 = 11  (9)
11 - 10 = 1 (10)

编辑 6

#include <stdio.h>
unsigned int fun1 ( unsigned int a, unsigned int b )
{
    unsigned int c;
    c = 0;
    while(a>b)
    {
       a-=b;
       c++;
    }
    return(c);
}
unsigned int fun2 ( unsigned int a, unsigned int b )
{
    unsigned int res;
    unsigned int acc;
    unsigned int rb;

    res=0;
    acc=0;
    for(rb=0x80000000;rb;rb>>=1)
    {
        acc<<=1;
        if(rb&a) acc|=1;
        if(acc>=b)
        {
            acc-=b;
            res|=rb;
        }
    }
    return(res);
}
int main ( void )
{
    printf("%u\n",fun1(21,2));
    printf("%u\n",fun1(1234,10));
    printf("%u\n",fun2(21,2));
    printf("%u\n",fun2(1234,10));
    return(0);
}
10
123
10
123

很明显，你对事物的大小有限制，你不能一般地放入任何两个值并让这些工作。

Answer 2

我的固定解：

uint32_t divide(uint32_t y, uint32_t x, uint32_t *q)
{
    (*q) = 0;
    if (y < x)
    {
        *q = 0;
        return y;
    }
    uint32_t tq = 0;
    uint32_t td = 0;
    int shift = 0;
    while (y >= x)
    {
        shift = bitlen(y) - bitlen(x);
        tq = (1 << shift);
        td = (x << shift);
        while (y <  td)
        {
            tq >>= 1;
            td >>= 1;
        }
        
        y -= (td);
        (*q) += tq;
            
    }
    return y;
}

为什么在这个二进制除法案例中左移商？

Why do you left shift the quotient in this binary division case?

c

binary

integer-division

编辑

编辑 2

编辑 3（固定）

编辑 4

编辑 5

编辑 6