¿Cómo determina la computadora si un número es menor o mayor que otro?

Puede sonar como una pregunta estúpida, pero tengo mucha curiosidad por saber cómo una computadora sabe que . Además, ¿cómo sabe una computadora que el orden de los enteros es 1 , 2 , 3 , 4 , 5 , ... y el alfabeto es A, B, C, D, ...? ¿Está almacenado en algún lugar en el hardware o el sistema operativo proporciona este tipo de información?$1<2$$1,2,3,4,5,\ldots$

Primero, sus números enteros se convierten en números binarios. Por ejemplo, el entero 2 se convierte a 0010.

La CPU utiliza un comparador digital :

Un comparador digital o 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 menor que o igual al otro número.

Los comparadores se utilizan en unidades centrales de procesamiento (CPU) y microcontroladores.

Fuente: https://en.wikipedia.org/wiki/Digital_comparator

En el hardware del comparador se utilizan algunas compuertas (AND, OR, NAND, NOR, XOR, etc.). Estas puertas toman entradas binarias y dan 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í 0y 1son voltajes electrónicos para la puerta.
1- Representa un voltaje de umbral que indica un voltaje positivo.
0- Representa el voltaje por debajo del umbral.

Por ejemplo, suponga que un comparador funciona con 5 voltios (se considera una explicación) y luego: el
voltaje de más de 3 voltios puede considerarse como binary-1.
El voltaje por debajo de 3 voltios se considerará comobinary-0

Si una puerta obtiene una entrada como 3.5 voltios y otra entrada como 2 voltios, entonces considera que, 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 modo que


aquí cada subíndice represente 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,
. . .

Como los números son binarios, los dígitos son 0 o 1 y la función booleana para la igualdad de cualquiera de los dos dígitos y> puede expresarse como

es 1 solo si y son iguales.

Para la igualdad de A y B, todas 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 AND como

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 desde el bit más significativo, avanzando gradualmente hacia los bits significativos más bajos hasta encontrar una desigualdad. Cuando se encuentra una desigualdad, si el bit correspondiente de A es 1 y el de B es 0, entonces concluimos que A> B. Esta comparación secuencial se puede expresar lógicamente como:

No solo "sabe", sino que siempre verifica. Básicamente, hace lo mismo que usted 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 iniciales 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 letras para que las comparaciones de números también den el orden "correcto" para las letras.

No es el sistema operativo el que compara los enteros, la CPU se encarga de eso. Está hecho a nivel de puertas lógicas, consulte estas diapositivas para ver cómo se puede hacer.

Sobre el alfabeto, en ASCII , los caracteres alfanuméricos y otros caracteres especiales se representan como enteros, por lo que compararlos también es una operación de comparación de enteros, que realiza la CPU.

En realidad, y para obtener la imagen completa, creo que sería bastante útil ver con sus propios ojos la ruta de datos de una CPU real, por ejemplo MIPS:

Como puede ver, en realidad hay una segunda salida de la ALU, que es una señal llamada Cero. Existe para realizar operaciones de ramificación rápidas, 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 ramificaciones. Por lo tanto, cuando crea una posibilidad de ramificación en su código como:

si (a <b) {...}

$~\Rightarrow$$~\Rightarrow$

Observe que la señal cero es una de las entradas de la compuerta AND que determina de dónde tomará el valor el contador de programa (PC): Suponiendo que la señal de rama es '1', ya que tenemos una operación de rama

• $\Rightarrow$
• $\Rightarrow$

Espero haberte ayudado a ver "debajo del capó". No dude en solicitar más análisis sobre este asunto. Muchas cosas 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 funciona con números de hasta un cierto tamaño. Hoy en día eso suele ser un número entero de 64 bits (ignoraremos los números de coma flotante; la idea será similar).

Entonces debemos reconocer que

1. Una CPU está almacenando números de hasta (digamos) 64 bits de largo en binario, en algún formato (probablemente un complemento de 2s pero no importa demasiado qué).

2. Una CPU no puede hacer nada de forma nativa con números más grandes que eso. Tenemos que escribir algoritmos de software si queremos comparar números más grandes.

$a$$b$

$a-b$$a-b$es menor que cero Lo hace con una única operación nativa que podría funcionar, a nivel de circuito, como los algoritmos de comparación que las otras respuestas han descrito. Se parecerá mucho a eso, pero todo implementado en circuitos (debido a que el número está en un máximo de 64 bits, este es un circuito de cierto tamaño que podemos conectar y pegar en la CPU). Dependiendo de cómo la CPU almacena números, podría ser aún más rápido porque podría ser que todos los números negativos tienen el primer bit establecido en uno, o algo así. De cualquier manera, solo hay un total de 64 bits, por lo que definitivamente podemos verificar si este número es negativo.

$a < b$$a \geq b$

Ahora, para números más grandes, tenemos que implementar algo en el software que utilizará estas pequeñas comparaciones como subrutinas.

Para responder a esta pregunta, permítanme señalar primero que hay al menos dos niveles de abstracción para los números de comparación en una computadora, el nivel de máquina y el nivel de software .

Comparar números a nivel de 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 debe haber instrucciones para saltos condicionales . Por ejemplo, los procesadores de la familia x86 de Intel admiten las instrucciones jnz(salto si no es cero), jne(salto no igual), etc. Si faltan, entonces la CPU no estaría completa en Turing. Las variables de las que depende el salto condicional se almacenan en los registros. Por lo tanto, estas instrucciones están cableadas en la arquitectura de la CPU como un circuito construido desde puertas lógicas. Esta es la única forma en que la CPU puede comparar dos números.

Comparar números a nivel de software

Si compara dos números, digamos en un programa de c ++, esto se traduce en código de máquina y, por lo tanto, se lleva a cabo a nivel de máquina. Sin embargo, tal comparación puede ser más compleja. Realmente depende del tipo de datos que utilizó cómo se traduce la comparación al código de 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 cabe en un registro, por lo tanto, el compilador desglosará la comparación en una secuencia de comparaciones en el nivel de código de máquina. Lo mismo se aplica para tipos de datos / estructuras de datos más complicados, 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 código de máquina.

Como comentario final, quiero señalar que las CPU estándar también pueden funcionar con diferentes representaciones de números (enteros con signo en representación de complemento 1 o 2, flotantes). También se pueden realizar comparaciones en otras partes de la computadora, como la GPU.

otras respuestas son buenas, simplemente lanzando otra para mayor consideración / perspicacia con un sabor / giro CS. se puede construir un FSM , una máquina de estados finitos, que puede comparar dos números binarios de cualquier longitud, comenzando por pares desde los bits más significativos y trabajando hasta el bit menos significativo (LSB). también se puede usar para conceptualizar el comparador digital que se proporciona 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 que es correcto por inducción simple. funciona de la siguiente manera:

• ingrese los dos primeros dígitos binarios como un par (a, b)
• si a = 1 yb = 0, el número de la izquierda es mayor.
• si a = 0 yb = 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 aparición de un bit que es uno y el otro es cero, después de una ejecución inicial de cero o más 1 idénticos. Un comparador digital de longitud finita hecho de compuertas o comparadores de 1 bit puede verse como basado en la fijación de la longitud de esta operación FSM a un número fijo de bits. (sí, existe una fuerte correspondencia entre todos los circuitos finitos y la "fijación de la longitud" de los cálculos de FSM).

Esto puede parecer un ejercicio teórico, pero en realidad, la lógica en el software para representar números de precisión arbitrarios opera de forma análoga a este FSM, excepto que está codificado en un bucle de computadora que puede verse como un bucle o simulando los pasos del FSM (una implementación eficiente podría rastrear a través de un índice la ubicación del MSB).

Además, razonablemente interpretemos / generalicemos esta pregunta como no limitada a enteros . la pregunta se refiere a números enteros pero el título solo se refiere a números. Sorprendentemente, nadie más ha mencionado la aritmética de coma flotante hasta ahora.

$a \times 10^b$$a$$b$