¿Las operaciones de cambio son O(1) o O(n)?¿Cambia el bit O (1) u O (n)?
¿Tiene sentido que las computadoras generalmente requieran más operaciones para cambiar 31 lugares en lugar de cambiar 1 lugar?
O ¿tiene sentido el número de operaciones requerida para el desplazamiento es constante independientemente del número de lugares que tenemos que cambiar?
PS: El preguntarse si hardware es una etiqueta adecuada ..
Algunos juegos de instrucciones están limitados a un cambio de bit por instrucción.Y algunos conjuntos de instrucciones le permiten especificar cualquier cantidad de bits para cambiar en una instrucción, que generalmente toma un ciclo de reloj en procesadores modernos (el ser moderno es una palabra intencionalmente vaga). Consulte dan04's answer sobre una palanca de cambio de barril, un circuito que cambia más de un bit en una operación.
Todo se reduce al algoritmo lógico. Cada bit en el resultado es una función lógica basada en la entrada. Para un solo desplazamiento a la derecha, el algoritmo sería algo así como:
Pero la ecuación lógica podría ser tan fácil:
Las puertas lógicas, al ser asíncronas, pueden hacer todo esto en un ciclo de reloj. Sin embargo, es cierto que el cambio único permite un ciclo de reloj más rápido y menos puertas para establecerse, si todo lo que está comparando son estos dos sabores de una instrucción. O la alternativa es hacer que tome más tiempo para establecerse, por lo que la instrucción toma 2 o 3 relojes o lo que sea, y la lógica cuenta a 3 y luego bloquea el resultado.
El MSP430, por ejemplo, solo tiene instrucciones rotatorias de un solo bit a la derecha (porque puede realizar un solo desplazamiento de bit o girar a la izquierda con otra instrucción, que dejaré al lector para que lo descubra).
El conjunto de instrucciones ARM permite giros de varios bits inmediatos y de registro, cambios aritméticos y cambios lógicos. Creo que solo hay una instrucción de rotación real y la otra es un alias, porque girar a la izquierda 1 es lo mismo que girar a la derecha 32, solo necesitas una palanca de cambios de una dirección para implementar una rotación de múltiples bits.
SHL en el x86 permite más de un bit por instrucción, pero solía llevar más de un reloj.
y así sucesivamente, puede examinar fácilmente cualquiera de los conjuntos de instrucciones que existen.
La respuesta a tu pregunta es que no se solucionó. Algunas veces es una operación, un ciclo, una instrucción. A veces es una instrucción de ciclos de reloj múltiples. A veces se trata de instrucciones múltiples, ciclos de reloj múltiples.
Los compiladores a menudo optimizan para este tipo de cosas. Supongamos que tiene un conjunto de instrucciones de registro de 16 bits con una instrucción de byte de intercambio y una instrucción AND con cambio inmediato, pero con solo un bit. Puede pensar que desplazar 8 bits requeriría 8 ciclos de instrucciones de desplazamiento, pero podría simplemente intercambiar bytes (una instrucción) y luego Y y la mitad inferior a ceros (lo que podría tomar dos instrucciones, o podría ser una instrucción de longitud de palabra variable de dos palabras, o puede codificar en una sola instrucción) por lo que solo se necesitan 2 o 3 ciclos de instrucción/reloj en lugar de 8. Para un cambio de 9 bits, puede hacer lo mismo y agregar un cambio, lo que lo convierte en 9 relojes frente a 3 o 4 Además, en algunas arquitecturas, es más rápido multiplicar por 256 que cambiar por 8, etc., etc. Cada conjunto de instrucciones tiene sus propias limitaciones y trucos.
Ni siquiera es el caso de que la mayoría de los conjuntos de instrucciones proporcionen múltiples bits o la mayoría de los límites a un solo bit. Los procesadores que entran en la categoría "computadora", como X86, ARM, PowerPC y MIPS, se inclinarían hacia una operación para cambiar. Expande a todos los procesadores, pero no necesariamente a las "computadoras" comúnmente utilizadas en la actualidad, y cambia para otro lado, yo diría que más de ellas son de un solo bit que de múltiples bits, por lo que se necesitan múltiples operaciones para realizar un cambio de múltiples bits.
desplazamiento de bits es O (1) en prácticamente cada procesador actual.
Observe, por ejemplo, en la instrucción x86 "shrw". El primer operando (en AT & sintaxis T) es el número de bits a desplazar. La forma en que un compilador implementa el desplazamiento depende del compilador, pero sería una tontería poner cambios en un ciclo cuando un procesador puede desplazar N bits de una vez.
Adición: : "¿Necesitan más operaciones para desplazarse a la izquierda 31?" Existen diferentes tipos de turnos (si se está preguntando por qué, considere qué hacer con los bits que se desplazan fuera del registro), pero la mayoría de los procesadores pueden realizar un cambio de una sola instrucción de tantos bits como pueda almacenar el GPR. Hacer un cambio de 40 bits en un registro de 32 bits requeriría desplazarse a través de múltiples registros (suponiendo que un número de 64 bits esté almacenado en 2 registros de 32 bits), que en cada procesador que conozco requerirá más instrucciones. Todavía sería O (1), probablemente no sea 1 reloj. Como nota interesante, el procesador Pentium IV es sorprendentemente lento en cambios de bit. Esto es irónico porque Intel históricamente ha recomendado la optimización de divisiones^2 y se multiplica por el cambio de bit. Vea: this PDF y Google para obtener más información si está interesado.
solo en 386+. cuando se usan recuentos de cambios arbitrarios en 286, es O (N) ya que los ciclos de reloj requeridos son 5 + n. –
@MarcB: Porque, por supuesto, todavía uso un 286, y por lo tanto necesito saber esto. : P –
¿Quiere decir que el 90% de los procesadores en estos días son como el x86 en el sentido de que pueden cambiar N bits de una vez? – Pacerier
Para hardware normal, los registros de tamaño fijo son constantes independientemente de la cantidad de lugares que cambie.
También tenga en cuenta, que el uso de la notación O es bastante raro aquí, que normalmente se utilizan para denotar la complejidad algorítmica basada en el número de no cambiar el número de plazas para cambiar ..
sí, pensé que la notación O es extraña aquí, pero de lo contrario el título sería muy largo ... – Pacerier
1) ¿Por normal, te refieres a moderno? 2) No encuentro la notación O extraña aquí en absoluto. –
1) Me refiero al 99.99% de la hw ... –
Un barrel shifter permite que el cambio se realice en O(log n) pasa — que se puede hacer en el mismo ciclo de reloj, haciendo que el cambio sea una operación O(1).
Ejem, lo probé por curiosidad en C# y obtuve resultados divertidos.
var sw = Stopwatch.StartNew();
long l = 1;
for (long i = 0; i < 20000000; i++) {
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
//...
// 50 of ^them^ total
}
Console.WriteLine(l + " " + sw.Elapsed);
Eso lleva 1.2 segundos en mi PC. Pero si reemplazo
l = l << 60; l = l >> 60;
con
l = l << 1; l = l >> 1;
entonces el tiempo aumenta a 2,0 seg. No tengo idea de qué tipo de optimizaciones están en juego aquí, pero se ve raro.
El hecho de que su compilador no haga cosas inteligentes no significa que las instrucciones no estén en el hardware. – Flexo
Realmente hace cosas inteligentes, ya que obtengo el mismo tiempo para todos los turnos que están entre 1 y 31 - 2.0 segundos. Luego obtengo 0.6 segundos si cambio exactamente 32 bits, pero de repente recibo solo 1.2 segundos si el número de turnos es mayor que 32. Eso es simplemente extraño. – user1096188
Es posible que sea mejor intentar esto en C en lugar de un lenguaje administrado. El jitter probablemente esté haciendo cosas debajo del capó que no estás viendo. –
Como ya se mencionó, una palanca de cambios puede desplazar un operando a una distancia arbitraria en tiempo constante. Sin embargo, una palanca de cambio de barril consume una buena cantidad de espacio en un dado de CPU, por lo que no están incluidas en todos los diseños de CPU.
Solo por un ejemplo bastante conocido, el Intel Pentium III incluía una palanca de cambios de barril, pero el Pentium IV no hizo ni. El código escrito para un Pentium III asumiendo que una palanca de cambio de barril estaba presente a veces disminuyó un poco en un Pentium IV. Tenía un código de cifrado (que incluye muchos cambios y rotaciones) que corría aproximadamente 4 veces más rápido en un Pentium III a 1.2 GHz que en un Pentium IV a 2.8 GHz.
¿Requieren más operaciones para desplazarse a la izquierda 31? – Flexo
Mi conocimiento de CPU es bastante antiguo, pero cada instrucción de cambio que he visto cambia un poco, por lo que necesita ejecutar un ciclo para cambiar más de una vez. Supongo que es posible que las CPU modernas tengan instrucciones de desplazamiento que cambien en un número específico de bits en un ciclo de reloj. –
En mi máquina 'int test (int i) { return i << 30; } 'se convierte en' saltos $ 30,% eax' – Flexo