Divide por 10 usando turnos de bit?

É possível dividir um inteiro sem sinal por 10 usando deslocamentos de bits puros, adição, subtração e talvez multiplicar? Usando um processador com resources muito limitados e divisão lenta.

Veja o que o compilador da Microsoft faz ao compilar divisões por pequenas constantes integrais. Assuma uma máquina de 32 bits (o código pode ser ajustado de acordo):

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

O que está acontecendo aqui é que estamos multiplicando por uma aproximação aproximada de 1/10 * 2 ^ 32 e, em seguida, removendo o 2 ^ 32. Essa abordagem pode ser adaptada para diferentes divisores e diferentes larguras de bits.

Isso funciona muito bem para a arquitetura ia32, já que sua instrução IMUL colocará o produto de 64 bits em edx: eax, e o valor edx será o valor desejado. Viz (assumindo dividendo é passado em eax e quociente retornado em 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 

Mesmo em uma máquina com uma instrução de multiplicação lenta, isso será mais rápido do que uma divisão de software.

Embora as respostas dadas até agora correspondam à pergunta atual, elas não correspondem ao título. Então, aqui está uma solução fortemente inspirada pelo Hacker’s Delight que realmente usa apenas mudanças 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); } 

Eu acho que esta é a melhor solução para arquiteturas que não possuem uma instrução de multiplicação.

Claro que você pode se você pode viver com alguma perda de precisão. Se você conhece o intervalo de valor de seus valores de input, você pode chegar a uma mudança de bit e uma multiplicação que é exata. Alguns exemplos de como você pode dividir por 10, 60, … como é descrito neste blog para formatar o tempo da maneira mais rápida possível.

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

Seu, Alois Kraus

Considerando a resposta de Kuba Ober, há outro na mesma linha. Ele usa uma aproximação iterativa do resultado, mas eu não esperaria performances surpreendentes.

Vamos dizer que temos que encontrar x onde x = v / 10 .

Usaremos a operação inversa v = x * 10 porque ela tem a propriedade nice de que quando x = a + b , então x * 10 = a * 10 + b * 10 .

Vamos usar x como variável mantendo a melhor aproximação do resultado até o momento. Quando a pesquisa terminar, x manterá o resultado. Vamos definir cada bit b de x do mais significativo para o menos significativo, um por um, comparar final (x + b) * 10 com v . Se for menor ou igual a v , o bit b será definido em x . Para testar o próximo bit, simplesmente deslocamos b uma posição para a direita (dividir por dois).

Podemos evitar a multiplicação por 10 mantendo x * 10 e b * 10 em outras variables.

Isso produz o seguinte 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 obter o algoritmo de Kuba Ober, que evita a necessidade da variável x10 , podemos subtrair b10 de v e v10 . Neste caso, o x10 não é mais necessário. O algoritmo se torna

 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 

O laço pode ser desenrolado e os diferentes valores de b e b10 podem ser pré-calculados como constantes.

Bem divisão é subtração, então sim. Mude para a direita por 1 (divida por 2). Agora subtraia 5 do resultado, contando o número de vezes que você faz a subtração até que o valor seja menor que 5. O resultado é o número de subtrações que você fez. Ah, e a divisão provavelmente será mais rápida.

Uma estratégia híbrida de deslocamento à direita e divisão por 5 usando a divisão normal pode resultar em uma melhoria de desempenho se a lógica no divisor já não fizer isso para você.

Em arquiteturas que só podem mudar um lugar de cada vez, uma série de comparações explícitas contra potências decrescentes de duas multiplicadas por dez pode funcionar melhor do que a solução do prazer do hacker. Assumindo um 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; }