¿Cómo determina la computadora si un número es más pequeño o mayor que otro?
https://cs.stackexchange.com/questions/7074
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Puede sonar como una pregunta estúpida, pero tengo mucha curiosidad por saber cómo una computadora sabe que $ 1 <2 $? Además, ¿cómo sabe una computadora que el orden de entero es de $ 1,2,3,4,5, ldots $ y el alfabeto es A, B, C, D, ...? ¿Se almacena en algún lugar en el hardware o el sistema operativo proporciona este tipo de información?
Solución
Primero, sus números enteros se convierten en números binarios. Por ejemplo, el entero 2 se convierte en 0010.
La CPU usa una comparador digital:
A comparador digital o el comparador de magnitud es un dispositivo electrónico de hardware que toma dos números como entrada en forma binaria y determina si un número es mayor o menos o igual al otro número.
Los comparadores se utilizan en unidades de procesamiento central (CPU) y microcontroladores.
En hardware comparador se usan algunas puertas (y, o, nand, nor, xor, etc.). Estas puertas toman entradas binarias y dan el resultado en binario. La salida se puede ver desde una tabla de verdad.
Inputs Outputs
A B A>B A=B A<B
0 0 0 1 0
0 1 0 0 1
1 0 1 0 0
1 1 0 1 0
Aquí 0 & 1 son voltajes electrónicos para la puerta.
1 - Representa algún voltaje umbral que indica un voltaje positivo.
0 - Representa el voltaje a continuación que el umbral.
Por ejemplo, supongamos que un comparador funciona en 5 voltios (es consideración para la explicación) luego:
Voltaje más de 3 voltios puede considerarse como binary-1.
Voltaje inferior a 3 voltios se considerará como binary-0
Si una puerta obtiene una entrada como 3.5 voltios y otra entrada como 2 voltios, entonces considera como, toma una entrada como binaria 1 y otra entrada como binaria 0.
Estas secuencias de 1 y 0 se proporcionan muy rápidamente a través del circuito de conmutación.
El funcionamiento de un comparador digital de dos bits se puede expresar como una tabla de verdad:
Inputs Outputs
A1 A0 B1 B0 A>B A=B A<B
0 0 0 0 0 1 0
0 0 0 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
0 1 0 0 0 0 1
0 1 0 1 0 1 0
0 1 1 0 1 0 0
0 1 1 1 1 0 0
1 0 0 0 0 0 1
1 0 0 1 0 0 1
1 0 1 0 0 1 0
1 0 1 1 1 0 0
1 1 0 0 0 0 1
1 1 0 1 0 0 1
1 1 1 0 0 0 1
1 1 1 1 0 1 0
Para citar de Wikipedia:
Ejemplos: considere dos números binarios de 4 bits A y B de tal manera que
Aquí cada subíndice representa uno de los dígitos en los números.Igualdad
Los números binarios A y B serán iguales si todos los pares de dígitos significativos de ambos números son iguales, es decir,
.
.
.
Dado que los números son binarios, los dígitos son 0 o 1 y la función booleana para la igualdad de dos dígitos
y>
puede expresarse como
es 1 solo si
y
son iguales.
Para la igualdad de A y B, todos
Las variables (para i = 0,1,2,3) deben ser 1. Por lo tanto, la condición de calidad de A y B se puede implementar utilizando la operación y
La variable binaria (a = b) es 1 solo si todos los pares de dígitos de los dos números son iguales.Desigualdad
Para determinar manualmente el mayor de dos números binarios, inspeccionamos las magnitudes relativas de pares de dígitos significativos, comenzando a partir del bit más significativo, procediendo gradualmente hacia bits significativos más bajos hasta que se encuentra una desigualdad. Cuando se encuentra una desigualdad, si el bit correspondiente de A es 1 y el de B es 0, concluimos que A> B. Esta comparación secuencial se puede expresar lógicamente como:
Otros consejos
No solo "sabe", se verifica cada vez. Básicamente, hace lo mismo que haría: para comparar, verifica (desde la izquierda) qué número tiene el primer dígito que es más grande que el correspondiente en el otro número. Por supuesto, debe agregar ceros liderados al número más corto.
Las letras son solo números para la computadora. Los humanos han asignado números, por ejemplo Ascii o Unicode, a las letras para que las comparaciones de números también otorguen el orden "correcto" para las letras.
No es el sistema operativo que compara enteros, la CPU se está ocupando de ella. Está hecho a nivel de puertas lógicas, consulte estas diapositivas para ver cómo se puede hacer.
Sobre el alfabeto, en Ascii Alfanumérico y otros caracteres especiales se representan como enteros, por lo que compararlos también es una operación de comparación entera, que realiza la CPU.
En realidad, y para obtener la imagen completa de ella, creo que sería bastante útil ver con sus propios ojos el datapath de una CPU real, por ejemplo, MIPS:
Como puede ver, en realidad hay una segunda salida del ALU, que es una señal llamada Zero. Existe para realizar operaciones de rama rápida, después de determinar si los dos operandos de la comparación son iguales a cero o no, ya que la mayoría de las comparaciones dentro de un programa son sobre ramas. Por lo tanto, cuando crea una posibilidad de rama en su código como:
if (a <b) {...}
Esto se traduce al código de máquina, en MIPS, por ejemplo: blt s0, s1, si $ ~ Rectarrow $ Si a <b ejecuta las instrucciones en los soportes, de lo contrario, continúe con la ejecución fuera del if {}. Específicamente, esta instrucción es una pseudoinstrucción, lo que significa que se traduce en otras dos (simples) instrucciones MIPS $ ~ rectarrow $
SLT AT, S0, S1 y entonces bne at, cero, si (SLT: establecer menos que y bne: rama en no igual).
Observe que la señal cero es una de las entradas de la puerta y la puerta que determina dónde el contador del programa (PC) tomará su valor de: suponiendo que la señal de la rama sea '1', ya que tenemos una operación de rama
- Cero = 0 $ Rectarrow $ El resultado de la resta no fue igual a cero, por lo que el multiplexor elegirá la dirección del objetivo de la rama y la ejecución continuará a partir de la instrucción que dirige la rama.
- Cero = 1 $ Derecha $ El resultado fue 0 (a = b) y, por lo tanto, el MUX elige la dirección del sumador donde se calcula la dirección de la siguiente instrucción en ejecución normal (serie). No se ejecuta ningún salto como la condición (a <b) no es válida.
Espero haberte ayudado a ver "debajo del capó". Siéntase libre de solicitar un análisis más detallado sobre este asunto. ¡Muchas cosas que damos por sentado, las CPU las hacen de una manera muy fascinante!
Si quieres saber cómo lo hace una CPU real, es algo como esto.
Una CPU opera en números de solo hasta cierto tamaño. Hoy en día, eso suele ser enteros de 64 bits (ignoraremos los números de punto flotante; la idea será similar).
Entonces debemos reconocer que
Una CPU almacena números hasta (por ejemplo) 64 bits de largo en binario, en algún formato (probablemente 2S-COMPLEMENTO Pero no importa demasiado qué).
Una CPU no puede hacer nada de manera nativa con números más grandes que eso. Tenemos que escribir algoritmos de software si queremos comparar números más grandes.
Ok, digamos que tenemos dos números que cada uno encaja en un entero de 64 bits de tamaño normal. Di $ A $ y $ B $. ¿Cómo los compara el procesador? Por lo general, restará uno del otro (esa es una operación nativa única que se implementa en el hardware).
Ahora el procesador ha almacenado un solo número de $ AB $. Nuevamente, este número es como máximo 64 bits, por lo que se ajusta en un "registro" que tiene 64 bits de largo, que es donde almacenamos nuestros números para el cálculo. Ahora solo verifica si $ AB $ es menor que cero. Lo hace con una sola operación nativa que podría funcionar, en el nivel de circuito, como los algoritmos de comparación que las otras respuestas han descrito. Se parecerá mucho a esos, pero todos implementados en circuitos (porque el número está en MAX 64 bits, este es un circuito de cierta tamaño que podemos alambiar y pegarnos en la CPU). Dependiendo de cómo la CPU almacene números, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI, TI Puede ser aún más rápido porque podría ser que todos los números negativos tengan el primer bit establecido en uno, o algo así. De cualquier manera, solo hay 64 bits en total, por lo que definitivamente podemos verificar si este número es negativo.
Si es así, entonces sabemos $ a <b $; Si no, entonces sabemos $ a geq b $.
Ahora, para números más grandes, tenemos que implementar algo en software que use estas pequeñas comparaciones como subrutinas.
Para responder a esta pregunta, permítanme señalar primero que hay al menos dos niveles en la abstracción para los números de comparación en una computadora, el a nivel de máquina, y el nivel de software.
Comparación de números en el nivel de la máquina
En la computadora de hoy, la CPU tiene un rico conjunto de instrucciones. Estas instrucciones incluyen, por ejemplo, cargar una celda de memoria en un registro, incrementar un registro, agregar dos registros y muchos más. También tiene que haber instrucciones para saltos condicionales. Por ejemplo, los procesadores en la familia X86 de Intel apoyan las instrucciones jnz (saltar si no cero), jne (Salta no igual), y así sucesivamente. Si faltaran, la CPU no sería completa. Las variables de las cuales depende el salto condicional se almacenan en los registros. Por lo tanto, estas instrucciones están conectadas en la arquitectura de la CPU como una construcción de circuitos a partir de puertas lógicas. Esta es la única forma en que puede la CPU comparar dos números.
Comparación de números en el nivel de software
Si compara dos números, digamos en un programa C ++, esto se traduce en código de máquina y, por lo tanto, se lleva a cabo en el nivel de la máquina. Sin embargo, tal comparación puede ser más compleja. Realmente depende del tipo de datos que haya utilizado cómo se traduce la comparación en el código de la máquina. Solo un ejemplo, los números que desea comparar son de las palabras de 64 bits, pero su máquina solo funciona con 32 bits. Entonces, este número no encaja en un registro, por lo tanto, el compilador desglosará la comparación en una secuencia de comparaciones en el nivel del código de la máquina. Lo mismo se aplica a tipos de datos/estructuras de datos más complicadas, que representan, por ejemplo, números racionales, cadenas o caracteres. Por lo tanto, cuando tiene que comparar dos caracteres, esto se traduce por software (sistema operativo, compilador, intérprete, ...) en el código de la máquina. La traducción real depende de la codificación del carácter/número.
Como comentario final, quiero señalar que las CPU estándar también pueden funcionar con diferentes representaciones de números (enteros firmados en representación de 1 o 2 complemento, flotadores). También se pueden realizar comparaciones en otras partes de la computadora, como la GPU.
Otras respuestas son buenas, solo arrojando otra por ahí para una mayor consideración/información con un sabor/giro CS. uno puede construir un FSM, una máquina de estado finito, que puede comparar dos números binarios de cualquier longitud, comenzar a pares desde los bits más significativos y trabajar a bit (LSB) menos significativo. También se puede utilizar para conceptualizar el comparador digital dado en otra respuesta, sin embargo, el FSM no requiere números binarios de longitud finita. Incluso puede funcionar en enteros con fracciones binarias después del LSB. Tiene un sabor inductivo y recursivo y puede demostrarse correctamente mediante una simple inducción. se ejecuta de la siguiente manera:
- Ingrese los dos dígitos binarios superiores como un par (A, B)
- Si a = 1 y b = 0 el número de izquierda es mayor.
- Si a = 0 y b = 1, el número correcto es mayor.
- De lo contrario, los números son "iguales hasta ahora", avance al siguiente par.
En otras palabras, el número más grande es el que tiene la primera ocurrencia de un bit que es uno y el otro es cero, después de una ejecución inicial de cero o más idéntico. Un comparador digital de longitud finita hecho de puertas o comparadores de 1 bits puede verse como basado en la fijación de la longitud de esta operación FSM a algún número fijo de bits. (Sí, existe una fuerte correspondencia entre todos los circuitos finitos y "fijar la longitud" de los cálculos FSM).
Esto puede parecer un ejercicio teórico, pero en realidad, la lógica en el software para representar precisión arbitraria números opera algo análogo a este FSM, excepto codificado en un bucle de computadora que puede verse como un bucle o simulando los pasos del FSM (una implementación eficiente puede rastrear a través de un índice de la ubicación del MSB).
Además, interpretemos razonablemente/generalizemos esta pregunta como no limitado a enteros. La pregunta se refiere a enteros, pero el título solo se refiere a números. Sorprendentemente, nadie más mencionó aritmética de punto flotante hasta aquí.
básicamente eso funciona comparando el exponente y el mantissa donde un número está en la forma $ a veces 10^b $, $ a $ la Mantissa, b el exponente. La Mantissa se puede normalizar a un número donde el primer dígito siempre es cero. Luego, para comparar dos números, la lógica primero compara los exponentes $ B $, y si son desiguales, puede devolver un resultado sin comparar las mantissas (usando el circuito comparador). Si los exponentes son iguales, compara las mantissas.
