suma - resta de n numeros en c++
¿La multiplicación y división usando operadores de cambio en C en realidad es más rápida? (16)
La multiplicación y la división se pueden lograr utilizando operadores de bits, por ejemplo
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
y así.
¿Es realmente más rápido usar decir (i<<3)+(i<<1) para multiplicar con 10 que usar i*10 directamente? ¿Hay algún tipo de entrada que no pueda ser multiplicada o dividida de esta manera?
¿Es realmente más rápido usar decir (i << 3) + (i << 1) para multiplicar con 10 que usar i * 10 directamente?
Puede o no estar en su máquina: si le importa, mida su uso en el mundo real.
Un estudio de caso - de 486 a core i7
La evaluación comparativa es muy difícil de hacer de manera significativa, pero podemos ver algunos hechos. Desde http://www.penguin.cz/~literakl/intel/s.html#SAL y http://www.penguin.cz/~literakl/intel/i.html#IMUL obtenemos una idea de los ciclos de reloj x86 Necesario para el cambio aritmético y la multiplicación. Digamos que nos atenemos a "486" (el más nuevo de la lista), registros de 32 bits e inmediatos, IMUL toma 13-42 ciclos e IDIV 44. Cada SAL toma 2, y agrega 1, por lo que incluso con algunos de ellos juntos cambian la apariencia superficial como un ganador
Estos días, con el core i7:
(de http://software.intel.com/en-us/forums/showthread.php?t=61481 )
La latencia es 1 ciclo para una suma de enteros y 3 ciclos para una multiplicación de enteros . Puede encontrar las latencias y el rendimiento en el Apéndice C del "Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32", que se encuentra en http://www.intel.com/products/processor/manuals/ .
(de algún blurb de Intel)
Usando SSE, el Core i7 puede emitir instrucciones de adición y multiplicación simultáneas, lo que resulta en una tasa máxima de 8 operaciones de punto flotante (FLOP) por ciclo de reloj
Eso te da una idea de hasta dónde han llegado las cosas. La trivialidad de la optimización, como el cambio de bits versus * , que se ha tomado en serio incluso en los años 90, ahora está obsoleta. El cambio de bits es aún más rápido, pero para mul / div sin potencia de dos para cuando realiza todos los turnos y agrega los resultados, vuelve a ser más lento. Luego, más instrucciones significan más fallas de caché, más problemas potenciales en la canalización, más uso de registros temporales puede significar más ahorro y restauración del contenido del registro de la pila ... rápidamente se complica demasiado para cuantificar definitivamente todos los impactos, pero son predominantemente negativo.
Funcionalidad en código fuente vs implementación
Más generalmente, su pregunta está etiquetada como C y C ++. Como lenguajes de tercera generación, están diseñados específicamente para ocultar los detalles del conjunto de instrucciones de la CPU subyacente. Para satisfacer sus estándares de idioma, deben admitir las operaciones de multiplicación y cambio (y muchas otras) incluso si el hardware subyacente no lo hace . En tales casos, deben sintetizar el resultado requerido utilizando muchas otras instrucciones. De manera similar, deben proporcionar soporte de software para operaciones de punto flotante si la CPU no tiene una FPU. Todas las CPU modernas son compatibles con * y << , por lo que esto puede parecer absurdamente teórico e histórico, pero lo importante es que la libertad de elegir la implementación va en ambos sentidos: incluso si la CPU tiene una instrucción que implementa la operación solicitada en el código fuente en el caso general, el compilador es libre de elegir otra cosa que prefiera porque es mejor para el caso específico con el que se enfrenta el compilador.
Ejemplos (con un lenguaje ensamblador hipotético)
source literal approach optimised approach
#define N 0
int x; .word x xor registerA, registerA
x *= N; move x -> registerA
move x -> registerB
A = B * immediate(0)
store registerA -> x
...............do something more with x...............
Las instrucciones como exclusivo o ( xor ) no tienen ninguna relación con el código fuente, pero al borrar algo consigo mismo se borran todos los bits, por lo que se puede usar para establecer algo en 0. El código fuente que implica que las direcciones de memoria no implica que se utilicen. .
Este tipo de hacks se han utilizado durante tanto tiempo como las computadoras. En los primeros días de los 3GL, para asegurar la aceptación del desarrollador, la salida del compilador tenía que satisfacer al desarrollador de lenguaje de ensamblador de mano. Comunidad que el código producido no fue más lento, más detallado o peor. Los compiladores adoptaron rápidamente muchas grandes optimizaciones: se convirtieron en un almacén centralizado mejor que cualquier programador de lenguaje ensamblador individual, aunque siempre existe la posibilidad de que pierdan una optimización específica que resulta crucial en un caso específico: los humanos a veces pueden Resuélvalo y busque algo mejor mientras los compiladores hacen lo que se les ha dicho hasta que alguien les devuelva esa experiencia.
Por lo tanto, incluso si cambiar y agregar es aún más rápido en algún hardware en particular, es probable que el escritor del compilador haya funcionado exactamente cuando es seguro y beneficioso.
Mantenibilidad
Si su hardware cambia, puede volver a compilar y verá la CPU de destino y hará otra mejor elección, mientras que es poco probable que desee volver a visitar sus "optimizaciones" o enumerar qué entornos de compilación deberían usar la multiplicación y cuáles deberían cambiar. ¡Piense en todas las "optimizaciones" modificadas con un bit de no poder de dos escritas hace más de 10 años que ahora están ralentizando el código en el que se encuentran, ya que funciona con procesadores modernos ...!
Afortunadamente, los buenos compiladores como GCC pueden reemplazar una serie de desplazamientos de bits y aritmética con una multiplicación directa cuando cualquier optimización está habilitada (es decir, ...main(...) { return (argc << 4) + (argc << 2) + argc; } -> imull $21, 8(%ebp), %eax ) por lo que una recompilación puede ayudar incluso sin corregir el código, pero eso no está garantizado.
El extraño código de cambio de bits que implementa la multiplicación o división es mucho menos expresivo de lo que intentaba lograr conceptualmente, por lo que otros desarrolladores se confundirán con eso, y es más probable que un programador confundido introduzca errores o elimine algo esencial en un esfuerzo por restablecer la cordura. Si solo haces cosas que no son obvias cuando son realmente beneficiosas y luego las documentas bien (pero no documentes otras cosas que sean intuitivas de todos modos), todos estarán más felices.
Soluciones generales versus soluciones parciales.
Si tiene algún conocimiento adicional, como que su int realmente solo almacenará los valores x , y , z , entonces podrá elaborar algunas instrucciones que funcionen para esos valores y obtener su resultado más rápidamente que cuando el compilador no tiene esa visión y necesita una implementación que funcione para todos los valores de int . Por ejemplo, considere su pregunta:
La multiplicación y la división se pueden lograr utilizando operadores de bits ...
Usted ilustra la multiplicación, pero ¿qué hay de la división?
int x;
x >> 1; // divide by 2?
Según el estándar C ++ 5.8:
-3- El valor de E1 >> E2 es E1 posiciones de bit E2 desplazadas a la derecha. Si E1 tiene un tipo sin signo o si E1 tiene un tipo con signo y un valor no negativo, el valor del resultado es la parte integral del cociente de E1 dividido por la cantidad 2 elevada a la potencia E2. Si E1 tiene un tipo firmado y un valor negativo, el valor resultante se define por la implementación.
Entonces, su cambio de bit tiene un resultado definido de implementación cuando x es negativo: puede que no funcione de la misma manera en diferentes máquinas. Pero, / funciona mucho más predeciblemente. (Tampoco puede ser perfectamente consistente, ya que diferentes máquinas pueden tener diferentes representaciones de números negativos y, por lo tanto, diferentes rangos, incluso cuando hay el mismo número de bits que forman la representación).
Puede decir "No me importa ... que int es almacenar la edad del empleado, nunca puede ser negativo". Si tiene ese tipo de información especial, entonces sí, su >> compilación segura puede ser pasada por alto por el compilador a menos que lo haga explícitamente en su código. Pero es arriesgado y rara vez es útil, ya que la mayoría del tiempo no tendrá este tipo de información, y otros programadores que trabajan en el mismo código no sabrán que han apostado en la casa por algunas expectativas inusuales de los datos que usted conoce Estaré manejando ... lo que parece un cambio totalmente seguro podría ser contraproducente debido a su "optimización".
¿Hay algún tipo de entrada que no pueda ser multiplicada o dividida de esta manera?
Sí ... como se mencionó anteriormente, los números negativos tienen un comportamiento definido de implementación cuando se "dividen" por desplazamiento de bits.
Acabo de probar en mi máquina compilando esto:
int a = ...;
int b = a * 10;
Al desmontarlo produce salida:
MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift
Esta versión es más rápida que su código optimizado a mano con cambio y adición puros.
Realmente nunca se sabe qué va a generar el compilador, por lo que es mejor simplemente escribir una multiplicación normal y dejar que optimice la forma en que lo desea, excepto en casos muy precisos en los que sabe que el compilador no puede optimizar.
Además de todas las otras buenas respuestas aquí, permítanme señalar otra razón para no usar turno cuando quiere decir dividir o multiplicar. Nunca he visto a alguien introducir un error olvidando la relativa precedencia de la multiplicación y la suma. He visto errores introducidos cuando los programadores de mantenimiento olvidaron que "multiplicar" mediante un cambio es lógicamente una multiplicación pero no sintácticamente de la misma precedencia que la multiplicación. x * 2 + z y x << 1 + z son muy diferentes!
Si está trabajando con números , use operadores aritméticos como + - * / % . Si está trabajando en matrices de bits, use operadores de cambio de bits como & ^ | >> & ^ | >> . No los mezcle; una expresión que tiene tanto twitdling como aritmética es un error que está por ocurrir.
Depende completamente del dispositivo objetivo, idioma, propósito, etc.
Pixel crunching en un controlador de tarjeta de video? Muy probable, si!
¿Aplicación de negocios .NET para tu departamento? Absolutamente ninguna razón para siquiera mirar en ello.
Para un juego de alto rendimiento para un dispositivo móvil puede valer la pena estudiarlo, pero solo después de que se hayan realizado optimizaciones más sencillas.
En el caso de los enteros con signo y el turno derecho frente a la división, puede marcar la diferencia. Para los números negativos, el turno se redondea hacia el infinito negativo, mientras que la división se redondea hacia cero. Por supuesto, el compilador cambiará la división a algo más barato, pero generalmente lo hará a algo que tiene el mismo comportamiento de redondeo, ya que no puede probar que la variable no será negativa o simplemente no lo hace. cuidado. Entonces, si puede probar que un número no será negativo o si no le importa de qué manera se redondeará, puede hacer esa optimización de una manera que es más probable que haga una diferencia.
Esto depende del procesador y del compilador. Algunos compiladores ya optimizan el código de esta manera, otros no. Por lo tanto, debe verificar cada vez que su código deba optimizarse de esta manera.
A menos que necesite desesperadamente optimizar, no codificaría mi código fuente solo para guardar una instrucción de ensamblaje o un ciclo de procesador.
Estoy de acuerdo con la marcada respuesta de Drew Hall. La respuesta podría usar algunas notas adicionales sin embargo.
Para la gran mayoría de los desarrolladores de software, el procesador y el compilador ya no son relevantes para la pregunta. La mayoría de nosotros estamos mucho más allá del 8088 y MS-DOS. Tal vez solo sea relevante para aquellos que aún están desarrollando para procesadores integrados ...
En mi compañía de software, Matemáticas (agregar / sub / mul / div) se debe usar para todas las matemáticas. Mientras que Shift se debe utilizar al convertir entre tipos de datos, por ejemplo. Ushort a byte como n >> 8 y no n / 256.
Hay optimizaciones que el compilador no puede hacer porque solo funcionan para un conjunto reducido de entradas.
Abajo hay un código de ejemplo de c ++ que puede hacer una división más rápida haciendo un 64bits "Multiplicación por el recíproco". Tanto el numerador como el denominador deben estar por debajo de cierto umbral. Tenga en cuenta que debe compilarse para usar instrucciones de 64 bits para que sea realmente más rápido que la división normal.
#include <stdio.h>
#include <chrono>
static const unsigned s_bc = 32;
static const unsigned long long s_p = 1ULL << s_bc;
static const unsigned long long s_hp = s_p / 2;
static unsigned long long s_f;
static unsigned long long s_fr;
static void fastDivInitialize(const unsigned d)
{
s_f = s_p / d;
s_fr = s_f * (s_p - (s_f * d));
}
static unsigned fastDiv(const unsigned n)
{
return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc;
}
static bool fastDivCheck(const unsigned n, const unsigned d)
{
// 32 to 64 cycles latency on modern cpus
const unsigned expected = n / d;
// At least 10 cycles latency on modern cpus
const unsigned result = fastDiv(n);
if (result != expected)
{
printf("Failed for: %u/%u != %u/n", n, d, expected);
return false;
}
return true;
}
int main()
{
unsigned result = 0;
// Make sure to verify it works for your expected set of inputs
const unsigned MAX_N = 65535;
const unsigned MAX_D = 40000;
const double ONE_SECOND_COUNT = 1000000000.0;
auto t0 = std::chrono::steady_clock::now();
unsigned count = 0;
printf("Verifying.../n");
for (unsigned d = 1; d <= MAX_D; ++d)
{
fastDivInitialize(d);
for (unsigned n = 0; n <= MAX_N; ++n)
{
count += !fastDivCheck(n, d);
}
}
auto t1 = std::chrono::steady_clock::now();
printf("Errors: %u / %u (%.4fs)/n", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT);
t0 = t1;
for (unsigned d = 1; d <= MAX_D; ++d)
{
fastDivInitialize(d);
for (unsigned n = 0; n <= MAX_N; ++n)
{
result += fastDiv(n);
}
}
t1 = std::chrono::steady_clock::now();
printf("Fast division time: %.4fs/n", (t1 - t0).count() / ONE_SECOND_COUNT);
t0 = t1;
count = 0;
for (unsigned d = 1; d <= MAX_D; ++d)
{
for (unsigned n = 0; n <= MAX_N; ++n)
{
result += n / d;
}
}
t1 = std::chrono::steady_clock::now();
printf("Normal division time: %.4fs/n", (t1 - t0).count() / ONE_SECOND_COUNT);
getchar();
return result;
}
Las instrucciones de multiplicación de turnos y enteros tienen un rendimiento similar en la mayoría de las CPU modernas: las instrucciones de multiplicación de enteros fueron relativamente lentas en la década de 1980, pero en general esto ya no es cierto. Las instrucciones de multiplicación de enteros pueden tener una latencia más alta, por lo que aún puede haber casos en los que sea preferible un cambio. Lo mismo ocurre con los casos en los que puede mantener más unidades de ejecución ocupadas (aunque esto puede cortar en ambos sentidos).
Sin embargo, la división de enteros sigue siendo relativamente lenta, por lo que usar un cambio en lugar de una división por una potencia de 2 sigue siendo una victoria, y la mayoría de los compiladores implementarán esto como una optimización. Sin embargo, tenga en cuenta que para que esta optimización sea válida, el dividendo debe estar sin signo o debe ser positivo. ¡Para un dividendo negativo, el cambio y la división no son equivalentes!
#include <stdio.h>
int main(void)
{
int i;
for (i = 5; i >= -5; --i)
{
printf("%d / 2 = %d, %d >> 1 = %d/n", i, i / 2, i, i >> 1);
}
return 0;
}
Salida:
5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3
Entonces, si desea ayudar al compilador, asegúrese de que la variable o expresión en el dividendo esté explícitamente sin firmar.
No lo haga a menos que sea absolutamente necesario y su intención de código requiera cambios en lugar de multiplicación / división.
En un día normal, podría ahorrar algunos ciclos de la máquina (o perder, ya que el compilador sabe mejor qué optimizar), pero el costo no vale la pena: gasta tiempo en detalles menores en lugar de un trabajo real, mantener el código se vuelve más difícil y tus compañeros te maldecirán
Es posible que deba hacerlo para cálculos de alta carga, donde cada ciclo guardado significa minutos de tiempo de ejecución. Pero, debe optimizar un lugar a la vez y hacer pruebas de rendimiento cada vez para ver si realmente lo hizo más rápido o rompió la lógica de los compiladores.
Por lo general, cambiar es mucho más rápido que multiplicar en un nivel de instrucción, pero es posible que esté perdiendo el tiempo haciendo optimizaciones prematuras. El compilador puede realizar estas optimizaciones en tiempo de compilación. Hacerlo usted mismo afectará la legibilidad y posiblemente no afectará el rendimiento. Es probable que solo valga la pena hacer cosas como esta si ha realizado un perfil y ha descubierto que se trata de un cuello de botella.
En realidad, el truco de la división, conocido como "división mágica", en realidad puede generar enormes beneficios. Una vez más, primero debe hacer un perfil para ver si es necesario. Pero si lo usa, hay programas útiles para ayudarlo a determinar qué instrucciones se necesitan para la misma semántica de división. Aquí hay un ejemplo: http://www.masm32.com/board/index.php?topic=12421.0
Un ejemplo que he sacado del hilo de OP en MASM32:
include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient
Generaría
mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
mul edx
.endif
shr edx,16
Por lo que sé, en algunas máquinas la multiplicación puede requerir hasta 16 a 32 ciclos de máquinas. Así que sí , dependiendo del tipo de máquina, los operadores de cambio de bits son más rápidos que la multiplicación / división.
Sin embargo, ciertas máquinas tienen su procesador matemático, que contiene instrucciones especiales para la multiplicación / división.
Prueba de Python que realiza la misma multiplicación 100 millones de veces contra los mismos números aleatorios.
>>> from timeit import timeit
>>> setup_str = ''import scipy; from scipy import random; scipy.random.seed(0)''
>>> N = 10*1000*1000
>>> timeit(''x=random.randint(65536);'', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati
>>> timeit(''x=random.randint(65536); x*2'', setup=setup_str, number=N)
2.2799630165100098
>>> timeit(''x=random.randint(65536); x << 1'', setup=setup_str, number=N)
2.2616429328918457
>>> timeit(''x=random.randint(65536); x*10'', setup=setup_str, number=N)
2.2799630165100098
>>> timeit(''x=random.randint(65536); (x << 3) + (x<<1)'', setup=setup_str, number=N)
2.9485139846801758
>>> timeit(''x=random.randint(65536); x // 2'', setup=setup_str, number=N)
2.490908145904541
>>> timeit(''x=random.randint(65536); x / 2'', setup=setup_str, number=N)
2.4757170677185059
>>> timeit(''x=random.randint(65536); x >> 1'', setup=setup_str, number=N)
2.2316000461578369
Entonces, al hacer un cambio en lugar de la multiplicación / división por una potencia de dos en python, hay una leve mejora (~ 10% para la división; ~ 1% para la multiplicación). Si no es una potencia de dos, es probable que haya una desaceleración considerable.
Nuevamente, estos #s cambiarán dependiendo de su procesador, su compilador (o intérprete, lo hizo en Python para simplificar).
Al igual que con todos los demás, no optimice prematuramente. Escriba código muy legible, perfil si no es lo suficientemente rápido, y luego intente optimizar las partes lentas. Recuerde, su compilador es mucho mejor en optimización que usted.
Respuesta corta: No es probable.
Respuesta larga: su compilador tiene un optimizador que sabe cómo multiplicarse tan rápido como su arquitectura de procesador de destino es capaz. Su mejor opción es decirle al compilador su intención claramente (es decir, i * 2 en lugar de i << 1) y dejar que decida cuál es la secuencia de código de máquina / ensamblador más rápida. Incluso es posible que el propio procesador haya implementado la instrucción de multiplicación como una secuencia de cambios y agregados en el microcódigo.
En pocas palabras, no pases mucho tiempo preocupándote por esto. Si quieres cambiar, cambia. Si quieres multiplicar, multiplica. Haga lo que sea semánticamente más claro: sus compañeros de trabajo se lo agradecerán más adelante. O, más probablemente, maldecirte más tarde si haces lo contrario.
Solo un punto concreto de medida: hace muchos años, comparé dos versiones de mi algoritmo de hash:
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != ''/0'' ) {
h = 127 * h + (unsigned char)*s;
++ s;
}
return h;
}
y
unsigned
hash( char const* s )
{
unsigned h = 0;
while ( *s != ''/0'' ) {
h = (h << 7) - h + (unsigned char)*s;
++ s;
}
return h;
}
En cada máquina en la que lo comparé, la primera fue al menos tan rápida como la segunda. Algo sorprendente, a veces era más rápido (por ejemplo, en un Sun Sparc). Cuando el hardware no admitía la multiplicación rápida (y la mayoría no lo hacía entonces), el compilador convertiría la multiplicación en las combinaciones apropiadas de turnos y suma / sub. Y debido a que conocía el objetivo final, a veces podría hacerlo en menos instrucciones que cuando escribiste explícitamente los turnos y los agregados / subs.
Tenga en cuenta que esto era algo así como hace 15 años. Con suerte, los compiladores solo han mejorado desde entonces, por lo que puedes contar con que el compilador haga lo correcto, probablemente mejor de lo que podrías. (Además, la razón por la que el código se ve tan C''ish es porque fue hace más de 15 años. Obviamente, usaría std::string e iteradores hoy).
Creo que en el caso en que quieres multiplicar o dividir por una potencia de dos, no puedes equivocarte con el uso de operadores de cambio de bits, incluso si el compilador los convierte a un MUL / DIV, porque algunos procesadores hacen microcódigo (en realidad, un macro) de todos modos, así que para esos casos logrará una mejora, especialmente si el cambio es más de 1. O más explícitamente, si la CPU no tiene operadores de cambio de bits, será un MUL / DIV de todos modos, pero si la CPU tiene Operadores de bitshift, evita una rama de microcódigo y esto es menos instrucciones.
Estoy escribiendo un código ahora mismo que requiere muchas operaciones de duplicación / reducción a la mitad porque está trabajando en un árbol binario denso, y hay una operación más que sospecho podría ser más óptima que una adición: una izquierda (la potencia de dos se multiplica) ) cambio con una adición. Esto se puede reemplazar con un desplazamiento a la izquierda y un xor si el desplazamiento es más ancho que el número de bits que desea agregar, el ejemplo fácil es (i << 1) ^ 1, que agrega uno a un valor duplicado. Por supuesto, esto no se aplica a un cambio a la derecha (potencia de dos divisiones) porque solo un cambio a la izquierda (little endian) llena la brecha con ceros.
En mi código, estas operaciones de multiplicación / división por dos y potencias de dos operaciones se usan de manera muy intensa y como las fórmulas ya son bastante cortas, cada instrucción que se puede eliminar puede ser una ganancia sustancial. Si el procesador no es compatible con estos operadores de cambio de bits, no se producirá ninguna ganancia, pero tampoco habrá una pérdida.
Además, en los algoritmos que estoy escribiendo, representan visualmente los movimientos que se producen, por lo que en realidad son más claros. El lado izquierdo de un árbol binario es más grande y el derecho es más pequeño. Además de eso, en mi código, los números pares e impares tienen un significado especial, y todos los niños de la mano izquierda en el árbol son impares y los niños de la mano derecha, y la raíz, son iguales. En algunos casos, no lo he encontrado todavía, pero puede que, oh, en realidad, ni siquiera pensé en esto, x & 1 puede ser una operación más óptima en comparación con x% 2. x & 1 en un número par producirá cero, pero producirá 1 para un número impar.
Yendo un poco más allá de la identificación par / impar, si obtengo cero para x & 3, sé que 4 es un factor de nuestro número, y lo mismo para x% 7 para 8, y así sucesivamente. Sé que estos casos probablemente tienen una utilidad limitada, pero es bueno saber que se puede evitar una operación de módulo y, en su lugar, utilizar una operación lógica a nivel de bits, ya que las operaciones a nivel de bits son casi siempre las más rápidas y menos ambiguas para el compilador.
Estoy prácticamente inventando el campo de los árboles binarios densos, por lo que espero que la gente no entienda el valor de este comentario, ya que muy raramente la gente quiere realizar factorizaciones solo en potencias de dos, o solo multiplicar / dividir potencias de dos.