Implementar la división con el operador bit a bit

¿Cómo puedo implementar la división usando operadores de bits (no solo división por potencias de 2)?

Descríbelo en detalle.

La forma estándar de hacer división es implementando la división binaria larga. Esto implica la resta, por lo que siempre y cuando no descartes esto como una operación que no sea un poco sabio, entonces esto es lo que debes hacer. (Tenga en cuenta que puede, por supuesto, implementar la resta, muy tediosamente, utilizando operaciones lógicas a nivel de bit).

En esencia, si estás haciendo Q = N/D :

  1. Alinea los más significativos de N y D
  2. Calcule t = (N - D); .
  3. Si (t >= 0) , establezca el bit menos significativo de Q en 1 y configure N = t .
  4. Desplaza a la izquierda N por 1.
  5. Q desplazamiento a la izquierda por 1.
  6. Ve al paso 2.

Haz un bucle para todos los bits de salida (incluso fraccionarios) que necesites, luego aplica un turno final para deshacer lo que hiciste en el Paso 1.

División de dos números usando operadores bit a bit.

 #include  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  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; } 

Supongo que estamos discutiendo la división de enteros.

Considere que obtuve 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 compare (1501-5 * 300) con 30. Al final tenemos 5 * ( 10 ^ 1) = 50 como resultado de esta división.

Ahora convierta ambos 1501 y 30 en dígitos binarios. Entonces, en lugar de multiplicar 30 por (10 ^ x) para alinearlo con 1501, multiplicamos (30) en 2 bases con 2 ^ n para alinear. Y 2 ^ n se pueden convertir en posiciones n del cambio a la izquierda.

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 implementar eso 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> (numbeMaxBit -bits); } 

Todas estas soluciones son demasiado largas. La idea base 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(aq, b); return new Point(c + rx, ry); } 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 (bx - x != 0) { return x - bx; } else { return y - by; } } @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 firmar, 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 la división sin el operador de división: deberá incluir la resta. Pero luego es como si lo hicieras a mano (solo en base a 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 // // ie: 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 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 cambiamos los bits a la derecha, lo dividimos por 2

1010 -> 0101

0101 es 5

Entonces, en general, si quieres dividir por una potencia de 2, necesitas desplazarte hacia la derecha por el exponente al que subes dos, para obtener ese valor

entonces, por ejemplo, para dividir por 16, cambiarías por 4, como 2 ^^ 4 = 16.