math - and - bitwise operators python

¿Divide entre 10 usando cambios de bit?

Question

¿Es posible dividir un entero sin signo entre 10 usando cambios de bits puros, suma, resta y tal vez multiplicar? Usar un procesador con recursos muy limitados y una división lenta.

Answer 1

Aunque las respuestas dadas hasta ahora coinciden con la pregunta real, no coinciden con el título. Así que aquí hay una solución fuertemente inspirada por Hacker''s Delight que realmente usa solo cambios de bit.

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

Creo que esta es la mejor solución para arquitecturas que carecen de una instrucción múltiple.

Answer 2

Considerando la respuesta de Kuba Ober, hay otra en el mismo sentido. Utiliza una aproximación iterativa del resultado, pero no esperaría ninguna actuación sorprendente.

Digamos que tenemos que encontrar x donde x = v / 10 .

Usaremos la operación inversa v = x * 10 porque tiene la propiedad agradable de que cuando x = a + b , entonces x * 10 = a * 10 + b * 10 .

Deje usar x como variable con la mejor aproximación de resultado hasta ahora. Cuando la búsqueda termina, x mantendrá el resultado. Configuraremos cada bit b de x del más significativo al menos significativo, uno por uno, fin compare (x + b) * 10 con v . Si es menor o igual a v , entonces el bit b se establece en x . Para probar el siguiente bit, simplemente cambiamos b una posición a la derecha (dividir por dos).

Podemos evitar la multiplicación por 10 manteniendo x * 10 b * 10 en otras variables.

Esto produce el siguiente algoritmo para dividir v por 10.

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

Editar: para obtener el algoritmo de Kuba Ober que evita la necesidad de la variable x10 , podemos restar b10 de v y v10 lugar. En este caso, x10 ya no es necesario. El algoritmo se convierte

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

El bucle puede estar desenrollado y los diferentes valores de b y b10 pueden b10 como constantes.

Answer 3

En las arquitecturas que solo pueden cambiar un lugar a la vez, una serie de comparaciones explícitas contra poderes decrecientes de dos multiplicados por 10 podría funcionar mejor que la solución del deleite del hacker. Suponiendo un dividendo de 16 bits:

uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) /
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; // round the result (optional)
  return quotient;
}

Answer 4

Esto es lo que hace el compilador de Microsoft al compilar divisiones mediante pequeñas constantes integrales. Supongamos una máquina de 32 bits (el código se puede ajustar en consecuencia):

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

Lo que sucede aquí es que estamos multiplicando por una aproximación cercana a 1/10 * 2 ^ 32 y luego eliminando los 2 ^ 32. Este enfoque se puede adaptar a diferentes divisores y diferentes anchos de bit.

Esto funciona muy bien para la arquitectura ia32, ya que su instrucción IMUL colocará el producto de 64 bits en edx: eax, y el valor edx será el valor deseado. Viz (asumiendo que el dividendo se pasa en eax y el cociente devuelto en eax)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

Incluso en una máquina con una instrucción de multiplicación lenta, esto será más rápido que una división de software.

Answer 5

La división del pozo es resta, así que sí. Cambia a la derecha por 1 (divide por 2). Ahora resta 5 del resultado, contando la cantidad de veces que restas hasta que el valor sea menor que 5. El resultado es el número de restas que hiciste. Oh, y la división probablemente sea más rápida.

Una estrategia híbrida de cambio en ese momento dividir por 5 usando la división normal podría mejorar el rendimiento si la lógica en el divisor no lo hace por usted.

Answer 6

Por supuesto que puedes si puedes vivir con cierta pérdida de precisión. Si conoces el rango de valores de tus valores de entrada, puedes obtener un cambio de bit y una multiplicación que es exacta. Algunos ejemplos de cómo se puede dividir por 10, 60, ... como se describe en este blog para formatear el tiempo de la manera más rápida posible.

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

Atentamente, Alois Kraus