Comment l'ordinateur détermine-t-il si un nombre est plus petit ou plus grand qu'un autre?

Cela peut sembler une question stupide mais je suis vraiment curieux de savoir comment un ordinateur sait que ? De plus, comment un ordinateur sait-il que l'ordre des entiers est et que l'alphabet est A, B, C, D, ...? Est-il stocké quelque part dans le matériel ou le système d'exploitation fournit-il ce type d'informations?$1<2$$1,2,3,4,5,\ldots$

D'abord, vos nombres entiers sont convertis en nombres binaires. Par exemple, le nombre entier 2 est converti en 0010.

La CPU utilise un comparateur numérique :

Un comparateur numérique ou un comparateur d' amplitude est un dispositif électronique matériel qui prend deux nombres en entrée sous forme binaire et détermine si un nombre est supérieur ou inférieur ou égal à l'autre.

Les comparateurs sont utilisés dans les unités centrales de traitement (CPU) et les microcontrôleurs.

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

Dans le matériel de comparaison, certaines portes sont utilisées (ET, OU, NAND, NOR, XOR, etc.). Ces portes prennent des entrées binaires et donnent un résultat en binaire. Le résultat peut être vu à partir d'une table de vérité.

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

Ici 0et 1sont des tensions électroniques pour la porte.
1- Représente une tension de seuil qui indique une tension positive.
0- Représente la tension inférieure au seuil.

Supposons, par exemple, qu’un comparateur fonctionne avec une tension de 5 volts (il s’agit d’une explication): Une
tension supérieure à 3 volts peut être considérée comme binary-1.
Une tension inférieure à 3 volts sera considérée commebinary-0

Si une porte reçoit une entrée en tant que 3,5 volts et une autre en 2 volts, alors elle considère que, elle prend une entrée en binaire 1 et une autre en binaire 0.

Ces séquences de 1 et 0 sont fournies très rapidement via le circuit de commutation.

Le fonctionnement d'un comparateur numérique à deux bits peut être exprimé sous la forme d'une table de vérité:

 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

Pour citer Wikipedia :

Exemples: considérons deux nombres binaires A et B de 4 bits tels


qu'ici chaque indice représente l'un des chiffres des nombres.

Égalité

Les nombres binaires A et B seront égaux si toutes les paires de chiffres significatifs des deux nombres sont égales, c'est-à-dire
. . .

Comme les nombres sont binaires, les chiffres sont 0 ou 1 et la fonction booléenne pour l’égalité de deux chiffres et> peut être exprimée par

est 1 seulement si et sont égaux.

Pour l'égalité de A et B, toutes les variables (pour i = 0,1,2,3) doivent être 1. Ainsi, la condition de qualité de A et B peut être mise en œuvre à l'aide de l'opération AND en tant que

variable binaire (A = B). n'est égal à 1 que si toutes les paires de chiffres des deux nombres sont égales.

Inégalité

Afin de déterminer manuellement le plus grand des deux nombres binaires, nous inspectons les magnitudes relatives des paires de chiffres significatifs, en commençant par le bit le plus significatif, puis en progressant progressivement vers les bits significatifs inférieurs, jusqu'à ce qu'une inégalité soit constatée. Lorsqu'une inégalité est trouvée, si le bit correspondant de A est 1 et celui de B est 0, nous concluons que A> B. Cette comparaison séquentielle peut être exprimée logiquement comme suit:

Cela ne fait pas que "savoir", il vérifie chaque fois. En gros, il fait la même chose que vous: pour comparer, il vérifie (de gauche à gauche) quel numéro a le premier chiffre plus grand que celui correspondant dans l'autre nombre. Bien sûr, vous devez ajouter des zéros non significatifs au nombre le plus court.

Les lettres ne sont que des chiffres pour l'ordinateur. Les humains ont attribué des numéros aux lettres , par exemple ASCII ou Unicode , afin que les comparaisons de nombres donnent également l'ordre "correct" des lettres.

Ce n'est pas le système d'exploitation qui compare les nombres entiers, le processeur s'en occupe. Il est fait au niveau des portes logiques, veuillez vous référer à ces diapositives pour voir comment faire.

En ce qui concerne l’alphabet, les caractères alphanumériques ASCII et autres sont représentés sous forme d’entiers. Leur comparaison est donc également une opération de comparaison d’entiers effectuée par la CPU.

En fait, et pour en obtenir une image complète, je pense qu'il serait très utile de voir de vos propres yeux le chemin de données d'un processeur réel, par exemple MIPS:

Comme vous pouvez le constater, il y a en fait une deuxième sortie de l'ALU, qui est un signal appelé zéro. Il existe pour effectuer des opérations de branchement rapides, après avoir déterminé si les deux opérandes de la comparaison sont égaux à zéro ou non , car la plupart des comparaisons au sein d'un programme concernent des branches. Par conséquent, lorsque vous créez une possibilité de branche dans votre code, comme:

si (a <b) {...}

$~\Rightarrow$$~\Rightarrow$

Notez que le signal zéro est l’une des entrées de la porte ET qui détermine l’emplacement de la valeur du compteur de programme: En supposant que le signal de branche est «1», car nous avons une opération de branche

• $\Rightarrow$
• $\Rightarrow$

J'espère que je vous ai aidé à voir "sous le capot". N'hésitez pas à demander une analyse plus approfondie à ce sujet. Beaucoup de choses que nous prenons pour acquis, les CPU les font de manière très fascinante!

Si vous voulez savoir comment un processeur réel le fait, c'est comme ça.

Un processeur fonctionne sur des nombres allant jusqu’à une certaine taille. De nos jours, il s’agit généralement d’entiers de 64 bits (nous ignorerons les nombres à virgule flottante, l’idée sera similaire).

Donc, nous devrions reconnaître que

1. Un processeur stocke des nombres allant jusqu'à (disons) 64 bits en binaire, dans un format donné ( complément 2s probablement, mais peu importe quoi).

2. Un processeur ne peut nativement rien faire avec des nombres plus grands que cela. Nous devons écrire des algorithmes logiciels si nous voulons comparer des nombres plus grands.

$a$$b$

$a-b$$a-b$est inférieur à zéro. Cela se fait avec une seule opération native qui pourrait fonctionner, au niveau du circuit, comme les algorithmes de comparaison décrits par les autres réponses. Cela ressemblera beaucoup à ceux-là, mais tous seront implémentés dans des circuits (parce que le nombre est de 64 bits au maximum, il s'agit d'un circuit d'une certaine taille que nous pouvons connecter et coller à la CPU.) En fonction de la manière dont la CPU stocke les nombres, pourrait être encore plus rapide car il se pourrait que tous les nombres négatifs aient le premier bit réglé à un, ou quelque chose comme ça. Quoi qu'il en soit, il n'y a que 64 bits au total, nous pouvons donc vérifier si ce nombre est négatif.

$a < b$$a \geq b$

Maintenant, pour les plus grands nombres, nous devons implémenter quelque chose dans un logiciel qui utilisera ces petites comparaisons comme sous-routines.

Pour répondre à cette question, permettez-moi d'abord de souligner qu'il existe au moins deux niveaux d'abstraction pour les nombres de comparaison sur un ordinateur, le niveau de la machine et le niveau du logiciel .

Comparer les chiffres au niveau de la machine

Dans l'ordinateur d'aujourd'hui, le processeur dispose d'un riche ensemble d'instructions. Ces instructions incluent, par exemple, le chargement d’une cellule de mémoire dans un registre, l’incrémentation d’un registre, l’ajout de deux registres et bien d’autres encore. Il doit également y avoir des instructions pour les sauts conditionnels . Par exemple, les processeurs de la famille x86 d’Intel prennent en charge les instructions jnz(saut si différent de zéro), jne(saut différent), etc. Si ceux-ci manquaient, le processeur ne serait pas complet. Les variables dont dépend le saut conditionnel sont stockées dans les registres. Ainsi, ces instructions sont câblées dans l’architecture de la CPU sous la forme d’un circuit construit à partir de portes logiques. C'est la seule façon dont le processeur peut comparer deux nombres.

Comparer les chiffres au niveau du logiciel

Si vous comparez deux nombres, par exemple dans un programme c ++, ceci est traduit en code machine et donc exécuté au niveau de la machine. Cependant, une telle comparaison peut être plus complexe. Cela dépend vraiment du type de données que vous avez utilisé. La conversion est convertie en code machine. À titre d’exemple, les chiffres que vous souhaitez comparer proviennent des mots de 64 bits, mais votre machine ne fonctionne que sur 32 bits. Ensuite, ce nombre ne rentre pas dans un registre, par conséquent le compilateur décompose la comparaison en une séquence de comparaisons au niveau du code machine. Il en va de même pour les types de données / structures de données plus complexes, représentant par exemple des nombres rationnels, des chaînes ou des caractères. Par conséquent, lorsque vous devez comparer deux caractères, cela doit être traduit par le logiciel (système d'exploitation, compilateur, interprète, ...) en code machine.

En guise de conclusion, je tiens à souligner que les CPU standard peuvent également fonctionner avec différentes représentations de nombres (entiers signés dans une représentation à 1 ou 2 complément, flottants). Des comparaisons peuvent également être effectuées dans d'autres parties de l'ordinateur, telles que le GPU.

les autres réponses sont bonnes, en jetant simplement une autre pour plus de considération / perspicacité avec une saveur / torsion de CS. on peut construire un FSM , une machine à états finis, capable de comparer deux nombres binaires de n'importe quelle longueur, en commençant par paire à partir des bits de poids fort et en travaillant au bit de poids faible (LSB). il peut également être utilisé pour conceptualiser le comparateur numérique donné dans une autre réponse, mais le FSM ne nécessite pas de nombres binaires de longueur finie. il peut même fonctionner sur des entiers avec des fractions binaires après le LSB. il a une saveur inductive et récursive et peut être prouvé correct par simple induction. il fonctionne comme suit:

• entrez les deux premiers chiffres binaires sous forme d'une paire (a, b)
• si a = 1 et b = 0, le nombre de gauche est plus grand.
• si a = 0 et b = 1, le nombre correct est plus grand.
• sinon, les chiffres sont "égaux jusqu'à maintenant", passez à la paire suivante.

en d'autres termes, le plus grand nombre est celui avec la première occurrence d'un bit qui est l'un et l'autre est zéro, après une exécution initiale de zéro ou de plusieurs 1 identiques. un comparateur numérique de longueur finie constitué de grilles ou de comparateurs à 1 bit peut être considéré comme basé sur la fixation de la longueur de cette opération FSM à un nombre fixe de bits. (Oui, il existe une forte correspondance entre tous les circuits finis et la "fixation de la longueur" des calculs FSM.)

cela peut sembler être un exercice théorique, mais en réalité, la logique du logiciel pour représenter des nombres de précision arbitraires fonctionne de manière analogue à ce FSM, sauf qu’elle est codée dans une boucle informatique pouvant être vue comme une boucle ou une simulation des étapes du FSM (une implémentation efficace peut suivre via un index l'emplacement du MSB).

aussi, laisse raisonnablement interpréter / généraliser cette question comme n'étant pas limitée aux nombres entiers . la question fait référence à des nombres entiers mais le titre ne fait référence qu'à des nombres. étonnamment personne d'autre n'a mentionné l' arithmétique en virgule flottante jusqu'à présent.

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