¿Es posible dividir un entero sin signo entre 10 mediante el uso de cambios de bits puros, suma, resta y tal vez multiplicar? Usar un procesador con recursos muy limitados y una división lenta.¿Divide entre 10 usando cambios de bits?
Esto es lo que hace el compilador de Microsoft al compilar por divisiones pequeñas constantes integrales. Asumir una máquina de 32 bits (código se puede ajustar en consecuencia):
int32_t div10(int32_t dividend)
{
int64_t invDivisor = 0x1999999A;
return (int32_t) ((invDivisor * dividend) >> 32);
}
¿Qué está pasando aquí es que estamos multiplicando por una estrecha aproximación de 1/10 * 2^32 y luego retirar la 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. A saber: (dividendos suponiendo que se aprobó 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 va a ser más rápido que una división de software.
+1, y me gustaría enfatizar que el compilador hará esto por usted automáticamente cuando escriba "x/10" – Theran
hmm, ¿no hay alguna inexactitud numérica aquí? –
Siempre tendrá imprecisión numérica al hacer divisiones enteras: ¿qué obtiene cuando divide 28 por 10 usando números enteros? Respuesta: 2. –
La división de pozo es resta, por lo 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.
Por supuesto que puede si puede vivir con algunas pérdidas en la 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 dar formato a time the fastest way posible.
temp = (ms * 205) >> 11; // 205/2048 is nearly the same as /10
Suyo, Alois Kraus
Debe tener en cuenta que el valor intermedio '(ms * 205)' puede desbordarse. –
Si lo hace int ms = 205 * (i >> 11); Obtendrá valores incorrectos si los números son pequeños. Necesita un conjunto de pruebas para garantizar que, en un rango de valores determinado, los resultados sean correctos. –
esto es exacto para ms = 0..1028 –
Aunque las respuestas dadas hasta el momento coinciden con la pregunta real, no coinciden con el título. Así que aquí hay una solución fuertemente inspirada en 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 las arquitecturas que carecen de una instrucción de multiplicar.
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 para el 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;
}
Su código realiza 16 multiplicaciones por 10. ¿Por qué cree que su código es más rápido que el del hacker? – chmike
No importa lo que pienso. Lo que importa es si en la plataforma aplicable es más rápido. Pruébalo! No hay una solución universalmente más rápida aquí en absoluto. Cada solución tiene alguna plataforma en mente y funcionará mejor en esa plataforma, posiblemente mejor que cualquier otra solución. –
No noté que n * 10 es constante. Así será precalculado por el compilador. Proporcioné un algoritmo alternativo en una respuesta. Nuestro algoritmo es equivalente excepto por una diferencia. Usted resta b * 10 de v y lo agrego a x * 10. Su algoritmo no necesita realizar un seguimiento de x * 10 que guarda una variable. El código que muestra desenrolla el ciclo my while. – chmike
Considerando la respuesta de Kuba Ober, hay otra en el mismo sentido. Utiliza una aproximación iterativa del resultado, pero no esperaría ningún rendimiento sorprendente.
Digamos que tenemos que encontrar x donde x = v/10.
Usaremos la operación inversa v = x * 10 porque tiene la buena propiedad de que cuando x = a + b, entonces x * 10 = a * 10 + b * 10.
Deje de usar x como variable con la mejor aproximación del resultado hasta el momento. Cuando finaliza la búsqueda, x contendrá el resultado. Configuraremos cada bit b de x de la más significativa a la menos significativa, una por una, comparando al final (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 y 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 poder iniciar el algoritmo de Kuba Ober que evita la necesidad de la variable x10, podemos restar b10 de v y v10 en su lugar. En este caso, ya no es necesario x10. El algoritmo convierte en
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 ser unwinded y los diferentes valores de b y b10 puede ser precalculados como constantes.
Es posible (resta repetida es división), pero la pregunta es si es más rápido que la división lenta. –
@esnyder. Lo siento, no te puedo entender. ¿Hablas en base 17 o base 22? –
Base dos grandes. El desplazamiento a la derecha se divide por 2^n, lo que resolvería tu pregunta si por "10" quieres decir 16 decimales o 10h. – tamarintech