¿Dividir por 10 usando cambios de bits?

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

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 multiply.

Por supuesto que puedes si puedes vivir con alguna pérdida de precisión. Si conoce el rango de valores de sus valores de entrada, puede llegar a un cambio de bits y una multiplicación que sea 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

Tuyo, Alois Kraus

Considerando la respuesta de Kuba Ober, hay otra en la misma línea. 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 nice que cuando x = a + b, entonces x * 10 = a * 10 + b * 10.

Vamos a usar x como variable que tiene la mejor aproximación del resultado hasta ahora. Cuando la búsqueda termine, x mantendrá el resultado. Lo haremos establezca cada bit b de x del más significativo al menos significativo, uno por uno, compare (x + b) * 10 con v. Si su menor o igual a v, entonces el bit b se establece en x. Para probar el siguiente bit, simplemente desplazamos 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 obtener el algoritmo de Kuba Ober que evita la necesidad de variable x10, podemos restar b10 de v y v10 en su lugar. En este caso x10 ya no es necesario. El algoritmo se 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 desenrollado y los diferentes valores de b y b10 pueden ser precalculados como constantes.

Bien la división es resta, así que sí. Cambiar a la derecha por 1 (dividir por 2). Ahora resta 5 del resultado, contando el número de veces que haces la resta hasta que el valor sea menor que 5. El resultado es el número de restas que hiciste. Ah, y dividir es probablemente va a ser más rápido.

Una estrategia híbrida de shift right then divide por 5 usando la división normal podría obtener una mejora en el rendimiento si la lógica en el divisor no lo hace ya por usted.

En arquitecturas que solo pueden cambiar un lugar a la vez, una serie de comparaciones explícitas contra potencias decrecientes de dos multiplicadas por 10 podría funcionar mejor que la solución de hacker's delight. 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;
}