Como o computador determina se um número é menor ou maior que outro?

Pode parecer uma pergunta estúpida, mas estou realmente curioso para saber como um computador sabe disso ? Além disso, como um computador sabe que a ordem do número inteiro é 1 , 2 , 3 , 4 , 5 , … e o alfabeto é A, B, C, D, ...? Está em algum lugar armazenado no hardware ou o sistema operacional fornece esse tipo de informação?$1<2$$1,2,3,4,5,\ldots$

Primeiro, seus números inteiros são convertidos em números binários. Por exemplo, o número inteiro 2 é convertido em 0010.

A CPU usa um comparador digital :

Um comparador digital ou comparador de magnitude é um dispositivo eletrônico de hardware que recebe dois números como entrada em formato binário e determina se um número é maior ou menor que ou igual ao outro número.

Os comparadores são usados ​​em unidades de processamento central (CPU) e microcontroladores.

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

No hardware do comparador, algumas portas são usadas (AND, OR, NAND, NOR, XOR, etc). Esses portões recebem entradas binárias e resultam em binárias. A saída pode ser vista em uma tabela verdade.

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

Aqui 0e 1são tensões eletrônicos para o portão.
1- Representa alguma tensão limite que indica alguma tensão positiva.
0- Representa a tensão abaixo do limite.

Por exemplo, suponha que um comparador funcione em 5 volts (é considerado uma explicação) então:
Tensão superior a 3 volts pode ser considerada binary-1.
Tensão abaixo de 3 volts será considerada comobinary-0

Se um gate obtém uma entrada como 3,5 volts e outra como 2 volts, considera-o como uma tomada binária 1 e outra como binário 0.

Essas seqüências de 1 e 0 são fornecidas muito rapidamente através do circuito de comutação.

A operação de um comparador digital de dois bits pode ser expressa como uma tabela de verdade:

 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 a Wikipedia :

Exemplos: considere dois números binários de 4 bits A e B, de modo que


Aqui cada subscrito represente um dos dígitos nos números.

Igualdade

Os números binários A e B serão iguais se todos os pares de dígitos significativos de ambos os números forem iguais, ou seja
,. . .

Como os números são binários, os dígitos são 0 ou 1 e a função booleana para igualdade de dois dígitos e> pode ser expressa como

é 1 somente se e for igual.

Para a igualdade de A e B, todas as variáveis ​​(para i = 0,1,2,3) devem ser 1. Portanto, a condição de qualidade de A e B pode ser implementada usando a operação AND como

A variável binária (A = B) é 1 somente se todos os pares de dígitos dos dois números forem iguais.

Desigualdade

Para determinar manualmente o maior de dois números binários, inspecionamos as magnitudes relativas de pares de dígitos significativos, começando pelo bit mais significativo, avançando gradualmente em direção a bits significativos mais baixos até encontrar uma desigualdade. Quando uma desigualdade é encontrada, se o bit correspondente de A é 1 e o de B é 0, concluímos que A> B. Essa comparação seqüencial pode ser expressa logicamente como:

Ele não apenas "sabe", mas também verifica todas as vezes. Basicamente, ele faz o mesmo que você faria: para comparar, verifica (a partir da esquerda) qual número tem o primeiro dígito que é maior que o correspondente no outro número. Claro que você precisa adicionar zeros à esquerda no número menor.

Letras são apenas números para o computador. Os seres humanos atribuíram números, por exemplo, ASCII ou Unicode , às letras, para que as comparações de números também dêem a ordem "correta" às letras.

Não é o sistema operacional que compara números inteiros, a CPU está cuidando disso. É feito no nível das portas lógicas, consulte estes slides para ver como isso pode ser feito.

Sobre o alfabeto, em ASCII , os caracteres alfanuméricos e outros caracteres especiais são representados como números inteiros, portanto, compará-los também é uma operação de comparação de números inteiros, executada pela CPU.

Na verdade, e para obter a imagem completa, acho que seria bastante útil ver com seus próprios olhos o caminho de dados de uma CPU real, por exemplo, MIPS:

Como você pode ver, na verdade existe uma segunda saída da ALU, que é um sinal chamado Zero. Existe para executar operações de ramificação rápidas, após determinar se os dois operandos da comparação são iguais a zero ou não , pois a maioria das comparações em um programa é sobre ramificações. Portanto, quando você cria uma possibilidade de ramificação no seu código, como:

if (a <b) {...}

Isso é traduzido em código de máquina, em mips, por exemplo: blt s0, s1, If $~\Rightarrow$se a <b execute as instruções entre colchetes, continue com a execução fora do if {}. Especificamente, esta instrução é uma pseudo-instrução, o que significa que é traduzida em duas outras instruções (simples) do MIPS$~\Rightarrow$
slt em, s0, s1 e, em seguida, bne em, zero, se (slt: defina menor que & bne: ramifique em Diferente).

Observe que o sinal zero é uma das entradas da porta AND que determina de onde o contador do programa (PC) terá seu valor: Supondo que o sinal de ramificação seja '1', pois temos uma operação de ramificação

• Zero = 0 $\Rightarrow$ O resultado da subtração não foi igual a zero, portanto, o Multiplexador escolherá o endereço do destino da Filial e a execução continuará a partir das instruções que a filial lidera.
• Zero = 1 $\Rightarrow$O resultado foi 0 (a = b) e, portanto, o MUX escolhe o endereço do adicionador, onde é calculado o endereço da próxima instrução em execução normal (serial). Nenhum salto é executado porque a condição (a <b) é inválida.

Espero ter ajudado você a ver "sob o capô". Sinta-se à vontade para solicitar mais análises sobre esse assunto. Muitas coisas que tomamos como garantidas, as CPUs fazem isso de uma maneira muito fascinante!

Se você quiser saber como uma CPU real faz isso, é algo assim.

Uma CPU opera em números de apenas até um determinado tamanho. Atualmente, geralmente são números inteiros de 64 bits (ignoraremos números de ponto flutuante; a idéia será semelhante).

Então devemos reconhecer que

1. Uma CPU está armazenando números de até (digamos) 64 bits de comprimento em formato binário, em algum formato (provavelmente com 2s de complemento, mas não importa muito o quê).

2. Uma CPU não pode fazer nada com números maiores que isso. Temos que escrever algoritmos de software se quisermos comparar números maiores.

OK, digamos que temos dois números que se encaixam em um número inteiro de 64 bits de tamanho normal. Dizer$a$ e $b$. Como o processador os compara? Geralmente, subtrai um do outro (que é uma operação nativa única que é implementada no hardware).

Agora o processador armazenou um único número $a-b$. Novamente, esse número tem no máximo 64 bits, então ele se encaixa em um "registro" de 64 bits, que é onde armazenamos nossos números para cálculo. Agora apenas verifica se$a-b$é menor que zero. Isso é feito com uma única operação nativa que pode funcionar, no nível do circuito, como os algoritmos de comparação descritos pelas outras respostas. Ele será parecido com esses, mas todos implementados em circuitos (porque o número é de no máximo 64 bits, este é um circuito de tamanho determinado que podemos conectar e manter na CPU). Dependendo de como a CPU armazena números, ela pode ser ainda mais rápido, porque pode ser que todos os números negativos tenham o primeiro bit definido como um, ou algo assim. De qualquer forma, existem apenas 64 bits no total, para que possamos definitivamente verificar se esse número é negativo.

Se for, então sabemos $a < b$; se não, então sabemos$a \geq b$.

Agora, para números maiores, temos que implementar algo em software que usará essas pequenas comparações como sub-rotinas.

Para responder a essa pergunta, primeiro quero salientar que há pelo menos dois níveis de abstração para os números de comparação em um computador, no nível da máquina e no nível do software .

Comparando números no nível da máquina

No computador de hoje, a CPU possui um rico conjunto de instruções. Essas instruções incluem, por exemplo, carregar uma célula de memória em um registro, incrementar um registro, adicionar dois registros e muito mais. Também deve haver instruções para saltos condicionais . Por exemplo, os processadores da família x86 da Intel suportam as instruções jnz(pule se não for zero), jne(pule não igual) e assim por diante. Se esses itens estivessem ausentes, a CPU não estaria completa com Turing. As variáveis ​​das quais o salto condicional depende são armazenadas nos registradores. Portanto, essas instruções são cabeadas na arquitetura da CPU como um circuito construído a partir de portas lógicas. Esta é a única maneira como a CPU pode comparar dois números.

Comparando números no nível do software

Se você comparar dois números, digamos em um programa c ++, isso será traduzido para o código da máquina e, portanto, executado no nível da máquina. No entanto, essa comparação pode ser mais complexa. Realmente depende do tipo de dados que você usou como a comparação é traduzida em código de máquina. Apenas um exemplo, os números que você deseja comparar são das palavras de 64 bits, mas sua máquina funciona apenas com 32 bits. Então esse número não cabe em um registro, portanto, o compilador dividirá a comparação em uma sequência de comparações no nível do código da máquina. O mesmo se aplica a tipos / estruturas de dados mais complicados, representando, por exemplo, números racionais, seqüências de caracteres ou caracteres. Portanto, quando você precisa comparar dois caracteres, isso é traduzido por software (sistema operacional, compilador, intérprete, ...) em código de máquina.

Como observação final, quero ressaltar que as CPUs padrão também podem trabalhar com diferentes representações de números (números inteiros assinados na representação de 1 ou 2 complementos, flutuadores). Também podem ser realizadas comparações em outras partes do computador, como a GPU.

outras respostas são boas, basta lançar outra por aí para uma consideração / percepção mais aprofundada com um toque / sabor de CS. pode-se construir um FSM , uma máquina de estados finitos, que pode comparar dois números binários de qualquer comprimento, começando em pares a partir dos bits mais significativos e trabalhando no bit menos significativo (LSB). também pode ser usado para conceituar o comparador digital fornecido em outra resposta, mas o FSM não requer números binários de comprimento finito. pode até trabalhar em números inteiros com frações binárias após o LSB. tem um sabor indutivo e recursivo e pode ser comprovado correto por simples indução. é executado da seguinte maneira:

• insira os dois dígitos binários superiores como um par (a, b)
• se a = 1 eb = 0, o número esquerdo é maior.
• se a = 0 eb = 1, o número certo é maior.
• caso contrário, os números são "iguais até agora", avance para o próximo par.

em outras palavras, o maior número é aquele com a primeira ocorrência de um bit que é um e o outro é zero, após uma execução inicial de zero ou mais 1s idênticos. um comparador digital de comprimento finito feito de portas ou comparadores de 1 bit pode ser visto como baseado na fixação do comprimento dessa operação FSM em um número fixo de bits. (sim, existe uma forte correspondência entre todos os circuitos finitos e "fixação do comprimento" dos cálculos do FSM.)

isso pode parecer um exercício teórico, mas, na verdade, a lógica do software para representar números de precisão arbitrários opera algo análogo a esse FSM, exceto codificado em um loop de computador que pode ser visto repetindo ou simulando as etapas do FSM (uma implementação eficiente rastrear por um índice a localização do MSB).

Além disso, vamos interpretar / generalizar razoavelmente esta questão como não limitada a números inteiros . a pergunta se refere a números inteiros, mas o título se refere apenas a números. surpreendentemente ninguém mais mencionou aritmética de ponto flutuante até agora.

basicamente isso funciona comparando o expoente e a mantissa onde um número está na forma$a \times 10^b$, $a$a mantissa, b o expoente. a mantissa pode ser normalizada para um número em que o primeiro dígito é sempre diferente de zero. então, para comparar dois números, a lógica primeiro compara os expoentes$b$e, se forem desiguais, ele pode retornar um resultado sem comparar as mantissas (usando, digamos, o circuito comparador). se os expoentes são iguais, compara as mantissas.