¿Cómo puedo usar el cambio de bit para reemplazar la división de enteros?

Question

Entiendo cómo hacerlo para potencias de 2 así que esa no es mi pregunta.

Por ejemplo, si quiero encontrar el 5% de un número usando un desplazamiento de bit en vez de una división entera, ¿cómo lo calcularía?

Así que en lugar de (x * 20/19), podría hacer (x * 100 >> 11). Ahora bien, esto no está bien pero está cerca y llegué a él usando prueba y error. ¿Cómo puedo determinar el cambio más preciso posible para usar?

Answer 1

Bueno en general:

• obtener la factorización prima del número, que le descompone en N 2^k * reposo, entonces se puede usar el desplazamiento de bits en los dos poder. Ejemplo: 20 = 2^2 * 5, por lo que multiplicar por veinte, te había multiplicar por 5 y luego utilice desplazamiento de bits << 2
• Para utilizar desplazamiento de bits en los no dos poderes, observe lo siguiente para odd l: a * l = a * (l - 1) + a, ahora l - 1 es par y, por lo tanto, se descompone en dos potencias, para lo cual se aplica el "truco" de cambio de bit.

La división se puede construir de manera similar.

Answer 2

Lo mejor es dejar que el compilador lo haga por usted. Simplemente escriba

a/b 

en el idioma de su elección, y el compilador genera el bit twiddling.

EDITAR (espero que no le importa, yo estoy añadiendo un refuerzo a su respuesta:.

#include <stdio.h> 

int main(int argc, char **argv) { 
    printf("%d\n", argc/4); 
} 

Obviamente, la cosa más rápida de hacerlo es argc>>2 Vamos a ver lo que sucede:

 .file "so3.c" 
     .section  .rodata 
.LC0: 
     .string "%d\n" 
     .text 
.globl main 
     .type main, @function 
main: 
     pushl %ebp 
     movl %esp, %ebp 
     andl $-16, %esp 
     subl $16, %esp 
     movl 8(%ebp), %eax 
     movl %eax, %edx 
     sarl $31, %edx 
     shrl $30, %edx 
     leal (%edx,%eax), %eax 
     sarl $2, %eax 
     movl %eax, %edx 
     movl $.LC0, %eax 
     movl %edx, 4(%esp) 
     movl %eax, (%esp) 
     call printf 
     leave 
     ret 
     .size main, .-main 
     .ident "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3" 
     .section  .note.GNU-stack,"",@progbits 

yup, ahí está, sarl $2, %eax

EDIT 2 (Lo siento a la pila en, pero 20/19 es un poco más complicado ...)

acabo sustituido argc*20/19 para argc/4 y esta es la matemática que sale:

0000000100000f07  shll $0x02,%edi 
0000000100000f0a  movl $0x6bca1af3,%edx 
0000000100000f0f  movl %edi,%eax 
0000000100000f11  imull %edx 
0000000100000f13  sarl $0x03,%edx 
0000000100000f16  sarl $0x1f,%edi 
0000000100000f19  subl %edi,%edx 

Por lo tanto, el proceso es

• Multiply entrada por 4 (shll)
• carga (movl 0x ...) y se multiplica por (imull) una fracción de punto fijo obtener un resultado de 64 bits (esto es el código de 32-bit)
• Divide de orden alto 32 bits de resultado por 8 (SARL), tenga en cuenta cómo este maneja los números negativos
• Divide baja de 32 bits de resultado por INT_MAX (SARL) para obtener ya sea 0 o -1
• correctamente redondee el resultado de orden superior agregando 1 (restando -1) si es necesario.

Answer 3

Supongamos que quiere aproximar el 5% de x multiplicando por y y cambiando por n. Desde el 5% es 1/20 y un >> n = a/2 ⁿ, se quiere resolver

x/20 ≈ x * y/2 ⁿ (el símbolo "≈" significa "aproximadamente igual ")

que simplifica a

y ≈ 2 ⁿ/20

Así que si n = 11, entonces

y ≈ 2 ⁿ/20 = 2048/20 = 102 + 8/20

Así podemos establecer y = 102, que en realidad es mejor que el 100 que encontró por ensayo y error.

Generalmente, podemos jugar con n para ver si podemos obtener una mejor respuesta.

He calculado esto para la fracción 1/20, pero debe poder resolver esto para cualquier fracción p/q siguiendo el mismo método.

Answer 4

Supongamos que tiene la expresión a = b/c. Como hroptatyr mencionó, la multiplicación es bastante rápida (y es mucho más rápida que la división). Entonces la idea básica es transformar la división en multiplicación como: a = b * (1/c).

Ahora, todavía necesitamos división para el cálculo de reciproco 1/c, por lo que esto funcionaría solo si se conoce c antes. Mientras que para el cálculo de coma flotante es suficiente, para intereges tenemos que usar otro truco: podemos usar para recíproco del valor de c el valor some_big_number/c, por lo que finalmente calcularemos a2 = b * (some_big_number/c), que es igual a some_big_number * b/c. Como estamos interesados ​​en el valor de b/c, debemos dividir el resultado final entre some_big_number. Si se elige que sea un poder de 2, entonces la división final sería rápida.

ejemplo:

// we'll compute 1/20 of the input 
unsigned divide_by_20(unsigned n){ 
    unsigned reciprocal = (0x10000 + 20 - 1)/20; //computed at compile time, but you can precompute it manually, just to be sure 
    return (n * reciprocal) >> 16; 
} 

EDIT: una buena parte de este método es que se puede elegir cualquier método de redondeo para la División por la elección de la corrección (en este caso se trataba de 20 - 1 para el redondeo hacia cero).

Answer 5

No se puede hacer todo con turnos, en su lugar se necesita utilizar divisores 'mágicos' (ver el deleite de los hackers). La división mágica funciona multiplicando un número por otro número adecuadamente grande, enrollándolo de tal forma que arroje la respuesta de división (mul/imul es más rápido que div/idiv). Las constantes mágicas solo son únicas para cada primo, los múltiplos requieren un turno, por ejemplo: la división sin signo por 3 puede representarse (en 32 bit) como , la división por 6 sería (x * 0xAAAAAAAB) >> 1 división por 12 cambiaría por 2, 24 por 3 etc. (Es la serie geométrica 3 * (2^x), donde 0 < = x < 32)

Answer 6

¡No tiene sentido porque lo que estás tratando de hacer no optimiza el proceso resultante!

Oye, no leí en ninguna parte de su pregunta que tuviera intención de optimizar.

Electric Engg La gente nunca deja de ser curiosa independientemente de su "utilidad". Somos como obsesivos obsesivos de artículos que lees en las noticias donde apilan sus desvanes, sótanos, dormitorios y salas de estar con basura que creen que algún día te vendrá bien. Al menos ese fue el caso cuando estaba en la escuela de Engg hace poco menos de 30 años. Te animo a que continúes en tu búsqueda para acumular conocimiento "inútil" que parece tener pocas posibilidades de optimizar tu vida o estilo de vida. ¿Por qué depender del compilador cuando puede hacerlo mediante un algoritmo codificado a mano? ¿Yah? Sé un poco aventurero, ya sabes. Ok, enuf, dissing personas que expresan desdén en su búsqueda del conocimiento.

¿Recuerdas en tu escuela media, la forma en que te enseñaron a hacer tu división? 437/24, p.

_____ 
24|437 


    018 
    ----- 
24|437 
    24 
    ----- 
    197 
    24 
    ----- 
    5 

El número que está sujeto a la división, 437, se denomina dividendo. 24 es el divisor, el resultado 18 es el cociente, y 5 es el resto. Al igual que cuando declara sus impuestos, debe completar los beneficios que había obtenido de los "dividendos" en existencia, lo cual es un nombre inapropiado. Lo que completa en el formulario de impuestos es un múltiplo del cociente de una gran porción de dividendo. No recibió el dividendo, sino porciones de dividendos; de lo contrario, significaría que poseía el 100% de las acciones.

 ___________ 
11000|110110101 



     000010010 
    ----------- 
11000|110110101 
     11000 
    ---------- 
     000110101 remainder=subtract divisor from dividend 
     11000000 shift divisor right and append 0 to quotient until 
     1100000 divisor is not greater than remainder. 
     110000 Yihaa! 
    ---------- 
     000101 remainder=subtract shifted divisor from remainder 
      11000 shift divisor right and append 0 to quotient until 
      1100 divisor is not greater than remainder. 
    ---------- 
       oops, cannot shift anymore. 

Lo anterior, como usted ya sabe, es la división TRUE. Lo cual se logra al restar por un divisor desplazado.

Lo que quiere es lograr lo mismo simplemente cambiando el dividendo. Eso, desafortunadamente no se puede hacer a menos que el divisor sea un poder exponencial de 2 (2,4,8,16). Lo cual es un hecho obvio de la aritmética binaria. O, al menos, no conozco ningún método que pueda hacerlo sin una aproximación y técnicas intrapolativas.

Por lo tanto, debe usar una combinación de cambio de dividendo y división verdadera. p.

24 = 2 x 2 x 2 x 3 

En primer lugar, dividir 437 por 8 utilizando desplazamiento binario para obtener 010010 y luego usar la verdadera división de dividir por 3:

010010 
    -------- 
11|110110 
    11 
    ------- 
    011 
     11 
    ----- 
     0 

lo que equivale a 010010 = 18.

Voila.

¿Cómo se determina 24 = 2^8 x 3?

Al desplazar hacia la derecha 11000 hasta llegar a un 1.

Lo que significa, que podría cambiar el dividendo el mismo número de veces que se desplazaría el divisor hasta que el divisor realiza un 1.

Por lo tanto, obviamente, este método no funcionaría si un divisor es impar. por ejemplo, no funcionará para el divisor 25, pero funcionará un poco para el divisor 50.

Puede haber, hay métodos predictivos que podrían interpolar un divisor como 13 para estar entre 2^3 = 8 y 2^4 = 16. Si hay, no estoy familiarizado con ellos.

Lo que necesita explorar es utilizar una serie numérica.Por ejemplo dividiendo por 25:

1 1 1  1  1 
__ = __ - ___ - ___ + ___ - ... until the precision you require. 
25 16 64 128 256 

donde la forma general de la serie es

1 1  b1    bn 
_ = ___ + _______ + ... + ______ 
D 2^k 2^(k+1)   2^(k+n) 

donde Bn es o bien -1, 0 o 1.

Espero que mi manipulación binaria anterior no tenga errores o errores tipográficos. Si es así, miles de disculpas.

Answer 7

Si está interesado en las matemáticas detrás de él, lea Hacker's Delight por Henry S. Warren.

Si está interesado en el código optimizado, simplemente escriba lo que es más fácil de leer por los seres humanos. Por ejemplo:

int five_percent(int x) { 
    return x/20; 
} 

Al compilar esta función utilizando g++ -O2, no va a hacer una división real pero algunos multiplicación magia, desplazamiento de bit y corrección en su lugar.