使用逐位运算符实现除法

Question

如何使用逐位运算符实现除法(不只是除以2的幂)？

详细描述.

Answer 1

进行除法的标准方法是实现二进制长除法.这涉及到减法,所以只要你不打算将其作为一个按位操作来折扣,那么这就是你应该做的.(注意,您当然可以使用按位逻辑运算非常繁琐地实现减法.)

从本质上讲,如果你这样做Q = N/D:

1. 对齐最重要的N和D.
2. 计算t = (N - D);.
3. 如果(t >= 0),则将最低有效位设置Q为1,然后设置N = t.
4. 左移N1.
5. 左移Q1.
6. 转到第2步.

根据需要循环输出多个输出位(包括小数),然后应用最后一个移位来撤消在步骤1中执行的操作.

Answer 2

使用按位运算符划分两个数字.

#include <stdio.h>

int remainder, divisor;

int division(int tempdividend, int tempdivisor) {
    int quotient = 1;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1;
    } else if (tempdividend < tempdivisor) {
        remainder = tempdividend;
        return 0;
    }   

    do{

        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;

     } while (tempdivisor <= tempdividend);


     /* Call division recursively */
    quotient = quotient + division(tempdividend - tempdivisor, divisor);

    return quotient;
} 


int main() {
    int dividend;

    printf ("\nEnter the Dividend: ");
    scanf("%d", &dividend);
    printf("\nEnter the Divisor: ");
    scanf("%d", &divisor);   

    printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
    printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);
    getch();
}

Answer 3

我假设我们正在讨论整数除法。

假设我有两个数字 1502 和 30，我想计算 1502/30。我们是这样做的：

首先，我们将 30 与最高有效数字 1501 对齐；30 变成 3000。然后将 1501 与 3000 进行比较，1501 包含 3000 中的 0。然后我们将 1501 与 300 进行比较，它包含 300 中的 5，然后将 (1501-5 300) 与 30 进行比较。最后我们得到 5 (10^ 1) = 50 作为该除法的结果。

现在将 1501 和 30 都转换为二进制数字。然后，我们不是将 30 乘以 (10^x) 以将其与 1501 对齐，而是将 2 进制的 (30) 乘以 2^n 来对齐。而2^n可以转化为左移n个位置。

这是代码：

int divide(int a, int b){
    if (b != 0)
        return;

    //To check if a or b are negative.
    bool neg = (a > 0) == (b > 0);

    //Convert to positive
    unsigned int new_a = (a < 0) ? -a : a;
    unsigned int new_b = (b < 0) ? -b : b;

    //Check the largest n such that b >= 2^n, and assign the n to n_pwr
    int n_pwr = 0;
    for (int i = 0; i < 32; i++)
    {
        if (((1 << i) & new_b) != 0)
            n_pwr = i;
    }

    //So that 'a' could only contain 2^(31-n_pwr) many b's,
    //start from here to try the result
    unsigned int res = 0;
    for (int i = 31 - n_pwr; i >= 0; i--){
        if ((new_b << i) <= new_a){
            res += (1 << i);
            new_a -= (new_b << i);
        }
    }

    return neg ? -res : res;
}

没有测试过，但你明白了。

Answer 4

int remainder =0;

int division(int dividend, int divisor)
{
    int quotient = 1;

    int neg = 1;
    if ((dividend>0 &&divisor<0)||(dividend<0 && divisor>0))
        neg = -1;

    // Convert to positive
    unsigned int tempdividend = (dividend < 0) ? -dividend : dividend;
    unsigned int tempdivisor = (divisor < 0) ? -divisor : divisor;

    if (tempdivisor == tempdividend) {
        remainder = 0;
        return 1*neg;
    }
    else if (tempdividend < tempdivisor) {
        if (dividend < 0)
            remainder = tempdividend*neg;
        else
            remainder = tempdividend;
        return 0;
    }
    while (tempdivisor<<1 <= tempdividend)
    {
        tempdivisor = tempdivisor << 1;
        quotient = quotient << 1;
    }

    // Call division recursively
    if(dividend < 0)
        quotient = quotient*neg + division(-(tempdividend-tempdivisor), divisor);
    else
        quotient = quotient*neg + division(tempdividend-tempdivisor, divisor);
     return quotient;
 }


void main()
{
    int dividend,divisor;
    char ch = 's';
    while(ch != 'x')
    {
        printf ("\nEnter the Dividend: ");
        scanf("%d", &dividend);
        printf("\nEnter the Divisor: ");
        scanf("%d", &divisor);

        printf("\n%d / %d: quotient = %d", dividend, divisor, division(dividend, divisor));
        printf("\n%d / %d: remainder = %d", dividend, divisor, remainder);

        _getch();
    }
}