两个数相除(位移)

二进制除法(binary division),通过移位和减法来实现

中英术语:

被除数 - dividend

除数 - divisor

商   - quotient


算法步骤:

Set quotient to 0
Align leftmost digits in dividend and divisor
Repeat
    If that portion of the dividend above the divisor is greater than or equal to the divisor
    Then
        subtract divisor from that portion of the dividend and
        Concatentate 1 to the right hand end of the quotient
    Else
        concatentate 0 to the right hand end of the quotient
    Shift the divisor one place right
Until dividend is less than the divisor
quotient is correct, dividend is remainder
STOP


例子

下面是 9/3 即
1001/11 例子

左边对齐,被除数只取左边除数的位数即 10
10    quotient=0
11

被除数小于除数,移入1位

100
 11

被除数大于等于除数,相减,商末尾连上1
100  -
 11
---------
001             quotient = 01

减后移入1位,此时被除数大于等于除数,继续相减,商末尾连上1
0011
  11
----------
0               quotient = 011


linux c例子

#include <stdio.h>

typedef struct {
    int n;
    int b_len;
} dl_int;


void b_div(dl_int *dividend, dl_int *divisor)
{
    int quotient = 0;
    int s = dividend->b_len - divisor->b_len;

    dl_int dd,ds;

    if (dividend->n < divisor->n) {
        dd = *divisor;
        printf("quotient:%d\nremainder:%d\n", 0, dd.n);
        return;
    }

    dd.n = dividend->n >> s;
    dd.b_len = divisor->b_len;

    for(;;) {
        if (dd.n >= divisor->n) {
            dd.n -= divisor->n;
            quotient =  (quotient << 1) | 1;
        } else
            quotient = quotient << 1;

        if (s == 0)
            break;

        dd.n = (dd.n << 1) | ( ( dividend->n >> (--s) ) & 1);
        dd.b_len++;
    }

    printf("quotient:%d\nremainder:%d\n", quotient, dd.n);
}
  
int main()
{
    
    dl_int dd, ds;

    //1001
    dd.n = 9;
    dd.b_len = 4;
    //11
    ds.n = 3;
    ds.b_len = 2;
    b_div(&dd, &ds);

    //1010
    dd.n = 10;
    dd.b_len = 4;
    //11
    ds.n = 3;
    ds.b_len = 2;
    b_div(&dd, &ds);
}


参考:

Binary Division by Shift and Subtract

上一篇: 两个数相乘(位移)
下一篇: 位图-布隆过滤器
作者邮箱: 203328517@qq.com