Implemente la división con el operador bit-wise

División de dos números usando operadores bitwise.

#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();
}

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

Esta solución funciona perfectamente.

#include <stdio.h>

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

    if (dividend == divisor)
    {
        *remainder = 0;
        return 1;
    }

    else if (dividend < divisor)
    {
        *remainder = dividend;
        return 0;
    }

    while (divisor <= dividend)
    {
        divisor = divisor << 1;
        quotient = quotient << 1;
    }

    if (dividend < divisor)
    {
        divisor >>= 1;
        quotient >>= 1;
    }

    quotient = quotient + division(dividend - divisor, origdiv, origdiv, remainder);

    return quotient;
}

int main()
{
    int n = 377;
    int d = 7;
    int rem = 0;

    printf("Quotient : %d\n", division(n, d, d, &rem));
    printf("Remainder: %d\n", rem);

    return 0;
}

Asumo que estamos discutiendo la división de enteros.

Considere que tengo dos números 1502 y 30, y quería calcular 1502/30. Así es como hacemos esto:

Primero alineamos 30 con 1501 en su cifra más significativa; 30 se convierte en 3000. Y compare 1501 con 3000, 1501 contiene 0 de 3000. Luego comparamos 1501 con 300, contiene 5 de 300, luego comparamos (1501-5 * 300) con 30. En lo que por fin tenemos 5 * (10^1) = 50 como resultado de esta división.

Ahora convierte ambos 1501 y 30 en dígitos binarios. Entonces en lugar de multiplicar 30 con (10^x) para alinearlo con 1501, multiplicamos (30) en 2 base con 2^n para alinear. Y 2^n se puede convertir en posiciones de desplazamiento a la izquierda n.

Aquí está el código:

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

    //To check if a or b are negative.
    bool neg = false;
    if ((a>0 && b<0)||(a<0 && b>0))
        neg = true;

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

No lo probé, pero entiendes la idea.

El siguiente método es la implementación de la división binaria considerando que ambos números son positivos. Si la resta es una preocupación, podemos implementarla también usando operadores binarios.

Código

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator == 0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits>0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0 ? 1 : 0;
        subResult = (subResult << 1) |msbBit;
        if (subResult >= denominator) {
            subResult = subResult-denominator;
            qoutient = (qoutient << 1) | 1;
        }
        else {
            qoutient = qoutient << 1;
        }
        remainingBits--;
    }
    return qoutient;
}


-(int)getMaxBit:(int)inputNumber
{
    int maxBit =0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1 << i) ) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit += 1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit -bits);
}

Todas estas soluciones son demasiado largas. La idea básica es escribir el cociente (por ejemplo, 5=101) como 100 + 00 + 1 = 101.

public static Point divide(int a, int b) {

    if (a < b)
        return new Point(0,a);
    if (a == b)
        return new Point(1,0);
    int q = b;
    int c = 1;
    while (q<<1 < a) {
        q <<= 1;
        c <<= 1;
    }
    Point r = divide(a-q, b);
    return new Point(c + r.x, r.y);
}


public static class Point {
    int x;
    int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int compare(Point b) {
        if (b.x - x != 0) {
            return x - b.x;
        } else {
            return y - b.y;
        }
    }

    @Override
    public String toString() {
        return " (" + x + " " + y + ") ";
    }
}

Para enteros:

public class Division {

    public static void main(String[] args) {
        System.out.println("Division: " + divide(100, 9));
    }

    public static int divide(int num, int divisor) {
        int sign = 1;
        if((num > 0 && divisor < 0) || (num < 0 && divisor > 0))
            sign = -1;

        return divide(Math.abs(num), Math.abs(divisor), Math.abs(divisor)) * sign;
    }

    public static int divide(int num, int divisor, int sum) {
        if (sum > num) {
            return 0;
        }

        return 1 + divide(num, divisor, sum + divisor);
    }
}

Con las advertencias habituales sobre el comportamiento de C con los cambios, esto debería funcionar para cantidades sin signo independientemente del tamaño nativo de un int...

static unsigned int udiv(unsigned int a, unsigned int b) {
  unsigned int c = 1, result = 0;

  if (b == 0) return (unsigned int)-1 /*infinity*/;

  while (((int)b > 0) && (b < a)) { b = b<<1; c = c<<1; }

  do {
    if (a >= b) { a -= b; result += c; }
    b = b>>1; c = c>>1;
  } while (c);

  return result;
}

Implementar división sin operador de división: Tendrá que incluir la resta. Pero entonces es igual que lo haces a mano (solo en la base de 2). El código adjunto proporciona una función corta que hace exactamente esto.

uint32_t udiv32(uint32_t n, uint32_t d) {
    // n is dividend, d is divisor
    // store the result in q: q = n / d
    uint32_t q = 0;

    // as long as the divisor fits into the remainder there is something to do
    while (n >= d) {
        uint32_t i = 0, d_t = d;
        // determine to which power of two the divisor still fits the dividend
        //
        // i.e.: we intend to subtract the divisor multiplied by powers of two
        // which in turn gives us a one in the binary representation 
        // of the result
        while (n >= (d_t << 1) && ++i)
            d_t <<= 1;
        // set the corresponding bit in the result
        q |= 1 << i;
        // subtract the multiple of the divisor to be left with the remainder
        n -= d_t;
        // repeat until the divisor does not fit into the remainder anymore
    }
    return q;
}

Dado que las operaciones de bits inteligentes funcionan en bits que son 0 o 1, cada bit representa una potencia de 2, por lo que si tengo los bits

1010

Ese valor es 10.

Cada bit es una potencia de dos, así que si desplazamos los bits a la derecha, dividimos por 2

1010 --> 0101

0101 es 5

Por lo tanto, en general, si desea dividir por alguna potencia de 2, es necesario cambiar a la derecha por el exponente se eleva dos a, para obtener ese valor

Así que, por ejemplo, para dividir por 16, cambiaría por 4, como 2^^4 = 16.