Nombre binaire - Binary number

Un nombre binaire est un nombre exprimé dans le système de numération de base 2 ou système de numération binaire , une méthode d'expression mathématique qui n'utilise que deux symboles : généralement " 0 " ( zéro ) et " 1 " ( un ).

Le système de numération en base 2 est une notation positionnelle avec une base de 2. Chaque chiffre est appelé bit , ou chiffre binaire. En raison de sa mise en œuvre simple dans les circuits électroniques numériques utilisant des portes logiques , le système binaire est utilisé par presque tous les ordinateurs et dispositifs informatiques modernes , en tant que système d'utilisation préféré, par rapport à diverses autres techniques humaines de communication, en raison de la simplicité du Langue.

Histoire

Le système de numération binaire moderne a été étudié en Europe aux XVIe et XVIIe siècles par Thomas Harriot , Juan Caramuel y Lobkowitz et Gottfried Leibniz . Cependant, des systèmes liés aux nombres binaires sont apparus plus tôt dans plusieurs cultures, notamment l'Égypte ancienne, la Chine et l'Inde. Leibniz s'est spécifiquement inspiré du I Ching chinois .

Egypte

Valeurs arithmétiques qui auraient été représentées par des parties de l' œil d'Horus

Les scribes de l'Egypte ancienne utilisaient deux systèmes différents pour leurs fractions, les fractions égyptiennes (non liées au système de nombres binaires) et les fractions Horus-Eye (ainsi appelées parce que de nombreux historiens des mathématiques croient que les symboles utilisés pour ce système pourraient être arrangés pour former l'œil d' Horus , bien que cela ait été contesté). Les fractions Horus-Eye sont un système de numérotation binaire pour les quantités fractionnaires de céréales, de liquides ou d'autres mesures, dans lequel une fraction d' hekat est exprimée comme la somme des fractions binaires 1/2, 1/4, 1/8, 1 /16, 1/32 et 1/64. Les premières formes de ce système se trouvent dans les documents de la cinquième dynastie de l' Egypte , environ 2400 avant JC, et ses dates de formulaire hiéroglyphiques pleinement développé à la dix - neuvième dynastie d'Egypte , environ 1200 av.

La méthode utilisée pour la multiplication égyptienne antique est également étroitement liée aux nombres binaires. Dans cette méthode, la multiplication d'un nombre par une seconde est effectuée par une séquence d'étapes dans laquelle une valeur (initialement le premier des deux nombres) est soit doublée, soit le premier nombre y est ajouté ; l'ordre dans lequel ces étapes doivent être effectuées est donné par la représentation binaire du deuxième nombre. Cette méthode peut être vue en usage, par exemple, dans le papyrus mathématique de Rhind , qui date d'environ 1650 av.

Chine

Taoïste Bagua

Le I Ching date du 9ème siècle avant JC en Chine. La notation binaire dans le I Ching est utilisée pour interpréter sa technique de divination quaternaire .

Il est basé sur la dualité taoïste du yin et du yang . Huit trigrammes (Bagua) et un ensemble de 64 hexagrammes ("soixante-quatre" gua) , analogues aux chiffres binaires à trois et six bits, étaient utilisés au moins dès la dynastie Zhou de la Chine ancienne .

L' érudit de la dynastie Song Shao Yong (1011-1077) a réorganisé les hexagrammes dans un format qui ressemble aux nombres binaires modernes, bien qu'il n'ait pas eu l'intention que son arrangement soit utilisé mathématiquement. Affichage du bit le moins significatif au-dessus des hexagrammes simples dans le carré de Shao Yong et lecture le long des rangées soit de bas à droite en haut à gauche avec des lignes pleines comme 0 et des lignes brisées comme 1 ou de haut à gauche en bas à droite avec des lignes pleines comme 1 et des lignes brisées car 0 hexagramme peut être interprété comme une séquence de 0 à 63.

Inde

Le savant indien Pingala (vers le IIe siècle av. J.-C.) a développé un système binaire pour décrire la prosodie . Il a utilisé des nombres binaires sous la forme de syllabes courtes et longues (ces dernières ayant une longueur égale à deux syllabes courtes), ce qui les rend similaires au code Morse . Ils étaient connus sous le nom de syllabes laghu (légère) et gourou (lourde).

Le classique hindou de Pingala intitulé Chandaḥśāstra (8.23) décrit la formation d'une matrice afin de donner une valeur unique à chaque mètre. "Chandaḥśāstra" se traduit littéralement par science des mètres en sanskrit. Les représentations binaires dans le système de Pingala augmentent vers la droite, et non vers la gauche comme dans les nombres binaires de la notation positionnelle moderne . Dans le système de Pingala, les nombres commencent à partir du numéro un et non de zéro. Quatre syllabes courtes "0000" est le premier modèle et correspond à la valeur un. La valeur numérique est obtenue en ajoutant un à la somme des valeurs de position .

Autres cultures

Les habitants de l'île de Mangareva en Polynésie française utilisaient un système hybride binaire- décimal avant 1450. Des tambours à fente avec des tons binaires sont utilisés pour encoder les messages à travers l'Afrique et l'Asie. Des ensembles de combinaisons binaires similaires au I Ching ont également été utilisés dans les systèmes de divination africains traditionnels tels que Ifá ainsi que dans la géomancie occidentale médiévale .

Les prédécesseurs occidentaux de Leibniz

À la fin du 13ème siècle, Ramon Llull avait l'ambition de rendre compte de toute la sagesse dans chaque branche de la connaissance humaine de l'époque. À cette fin, il a développé une méthode générale ou « Ars generalis » basée sur des combinaisons binaires d'un certain nombre de principes ou de catégories de base simples, pour lesquels il a été considéré comme un prédécesseur de l'informatique et de l'intelligence artificielle.

En 1605, Francis Bacon a discuté d'un système par lequel les lettres de l'alphabet pourraient être réduites à des séquences de chiffres binaires, qui pourraient ensuite être codés comme des variations à peine visibles de la police dans n'importe quel texte aléatoire. Fait important pour la théorie générale du codage binaire, il a ajouté que cette méthode pouvait être utilisée avec n'importe quel objet : « à condition que ces objets ne soient capables que d'une double différence ; comme par les cloches, par les trompettes, par les lumières et les torches, par le rapport des mousquets, et tout instrument de même nature". (Voir le chiffre de Bacon .)

John Napier a décrit en 1617 un système qu'il a appelé arithmétique de localisation pour effectuer des calculs binaires en utilisant une représentation non positionnelle par des lettres. Thomas Harriot a enquêté sur plusieurs systèmes de numérotation positionnelle, y compris binaire, mais n'a pas publié ses résultats ; ils ont été retrouvés plus tard dans ses papiers. Peut-être que la première publication du système en Europe a été de Juan Caramuel y Lobkowitz , en 1700.

Leibniz et le I Ching

Gottfried Leibniz

Leibniz a étudié la numérotation binaire en 1679 ; son travail apparaît dans son article Explication de l'Arithmétique Binaire (publié en 1703). Le titre complet de l'article de Leibniz est traduit en anglais par « Explication of Binary Arithmetic, qui n'utilise que les caractères 1 et 0, avec quelques remarques sur son utilité, et sur la lumière qu'elle jette sur les anciennes figures chinoises de Fu Xi » . Le système de Leibniz utilise 0 et 1, comme le système de numération binaire moderne. Un exemple du système de numération binaire de Leibniz est le suivant :

0 0 0 1 valeur numérique 2 0
0 0 1 0 valeur numérique 2 1
0 1 0 0 valeur numérique 2 2
1 0 0 0 valeur numérique 2 3

Leibniz a interprété les hexagrammes du I Ching comme une preuve du calcul binaire. En tant que sinophile , Leibniz connaissait le I Ching, notait avec fascination comment ses hexagrammes correspondaient aux nombres binaires de 0 à 111111, et concluait que cette cartographie était la preuve des principales réalisations chinoises dans le genre de mathématiques philosophiques qu'il admirait. La relation était une idée centrale de son concept universel d'une langue ou d'une caractéristique universalis , une idée populaire qui serait suivie de près par ses successeurs tels que Gottlob Frege et George Boole dans la formation de la logique symbolique moderne . Leibniz a d'abord été présenté au Yi King grâce à son contact avec le jésuite français Joachim Bouvet , qui a visité la Chine en 1685 en tant que missionnaire. Leibniz considérait les hexagrammes du Yi King comme une affirmation de l' universalité de ses propres croyances religieuses en tant que chrétien. Les chiffres binaires étaient au cœur de la théologie de Leibniz. Il croyait que les nombres binaires étaient symboliques de l'idée chrétienne de creatio ex nihilo ou de création à partir de rien.

[Un concept qui] n'est pas facile à transmettre aux païens, c'est la création ex nihilo par la toute-puissance de Dieu. Or on peut dire que rien au monde ne peut mieux présenter et démontrer cette puissance que l'origine des nombres, telle qu'elle est présentée ici à travers la présentation simple et sans fioritures du Un et du Zéro ou du Rien.

—  Lettre de Leibniz au duc de Brunswick jointe aux hexagrammes du I Ching

Développements ultérieurs

George Boole

En 1854, le mathématicien britannique George Boole a publié un article historique détaillant un système algébrique de logique qui deviendrait connu sous le nom d' algèbre booléenne . Son calcul logique allait devenir un instrument dans la conception de circuits électroniques numériques.

En 1937, Claude Shannon a produit sa thèse de maîtrise au MIT qui a mis en œuvre l'algèbre booléenne et l'arithmétique binaire à l'aide de relais et de commutateurs électroniques pour la première fois dans l'histoire. Intitulée A Symbolic Analysis of Relay and Switching Circuits , la thèse de Shannon fondait essentiellement la conception pratique de circuits numériques .

En Novembre 1937, George Stibitz , travaillait alors à Bell Labs , a complété un ordinateur à base de relais qu'il a baptisé le « modèle K » (pour « K itchen », où il avait assemblé il), qui a calculé en utilisant addition binaire. Bell Labs a autorisé un programme de recherche complet à la fin de 1938 avec Stibitz à la barre. Leur ordinateur à nombres complexes, achevé le 8 janvier 1940, était capable de calculer des nombres complexes . Lors d'une démonstration à la conférence de l' American Mathematical Society au Dartmouth College le 11 septembre 1940, Stibitz a pu envoyer des commandes à distance au Complex Number Calculator sur des lignes téléphoniques par un télétype . C'était la première machine informatique jamais utilisée à distance sur une ligne téléphonique. Certains participants à la conférence qui ont été témoins de la manifestation étaient John von Neumann , John Mauchly et Norbert Wiener , qui en ont parlé dans ses mémoires.

L' ordinateur Z1 , qui a été conçu et construit par Konrad Zuse entre 1935 et 1938, utilisait la logique booléenne et les nombres binaires à virgule flottante .

Représentation

N'importe quel nombre peut être représenté par une séquence de bits (chiffres binaires), qui à son tour peuvent être représentés par n'importe quel mécanisme capable d'être dans deux états mutuellement exclusifs. N'importe laquelle des lignes de symboles suivantes peut être interprétée comme la valeur numérique binaire de 667 :

1 0 1 0 0 1 1 0 1 1
| ?? | ?? ?? | | ?? | |
?? ?? ?? ?? ?? ?? ?? ?? ?? ??
oui m oui m m oui oui m oui oui
Une horloge binaire peut utiliser des LED pour exprimer des valeurs binaires. Dans cette horloge, chaque colonne de LED affiche un chiffre décimal codé en binaire de l' heure sexagésimale traditionnelle .

La valeur numérique représentée dans chaque cas dépend de la valeur attribuée à chaque symbole. Dans les premiers jours de l'informatique, des commutateurs, des trous perforés et des bandes de papier perforées étaient utilisés pour représenter des valeurs binaires. Dans un ordinateur moderne, les valeurs numériques peuvent être représentées par deux tensions différentes ; sur un disque magnétique , des polarités magnétiques peuvent être utilisées. Un état « positif », « oui » ou « activé » n'est pas nécessairement équivalent à la valeur numérique de un ; cela dépend de l'architecture utilisée.

Conformément à la représentation habituelle des chiffres en chiffres arabes , les nombres binaires sont généralement écrits à l' aide des symboles 0 et 1 . Lorsqu'ils sont écrits, les chiffres binaires sont souvent indicés, préfixés ou suffixés afin d'indiquer leur base, ou base. Les notations suivantes sont équivalentes :

  • 100101 binaire (déclaration explicite de format)
  • 100101b (suffixe indiquant le format binaire ; également connu sous le nom de convention Intel )
  • 100101B (un suffixe indiquant le format binaire)
  • bin 100101 (un préfixe indiquant le format binaire)
  • 100101 2 (un indice indiquant la notation base-2 (binaire))
  • %100101 (un préfixe indiquant le format binaire ; également connu sous le nom de convention Motorola )
  • 0b100101 (un préfixe indiquant le format binaire, courant dans les langages de programmation)
  • 6b100101 (un préfixe indiquant le nombre de bits au format binaire, courant dans les langages de programmation)
  • #b100101 (un préfixe indiquant le format binaire, courant dans les langages de programmation Lisp)

Lorsqu'ils sont prononcés, les chiffres binaires sont généralement lus chiffre par chiffre, afin de les distinguer des chiffres décimaux. Par exemple, le chiffre binaire 100 se prononce un zéro zéro , plutôt que cent , pour rendre sa nature binaire explicite et à des fins d'exactitude. Étant donné que le chiffre binaire 100 représente la valeur quatre, il serait déroutant de se référer au chiffre comme cent (un mot qui représente une valeur ou un montant complètement différent). Alternativement, le chiffre binaire 100 peut être lu comme "quatre" (la valeur correcte ), mais cela ne rend pas sa nature binaire explicite.

Compter en binaire


Nombre décimal

Nombre binaire
0 0
1 1
2 dix
3 11
4 100
5 101
6 110
7 111
8 1000
9 1001
dix 1010
11 1011
12 1100
13 1101
14 1110
15 1111

Le comptage en binaire est similaire au comptage dans n'importe quel autre système de numération. En commençant par un seul chiffre, le comptage s'effectue à travers chaque symbole, dans l'ordre croissant. Avant d'examiner le comptage binaire, il est utile de discuter brièvement du système de comptage décimal plus familier comme cadre de référence.

Comptage décimal

Le comptage décimal utilise les dix symboles 0 à 9 . Le comptage commence par la substitution incrémentielle du chiffre le moins significatif (chiffre le plus à droite) qui est souvent appelé le premier chiffre . Lorsque les symboles disponibles pour cette position sont épuisés, le chiffre le moins significatif est réinitialisé à 0 et le chiffre suivant de plus grande importance (une position à gauche) est incrémenté ( débordement ) et la substitution incrémentielle du chiffre de poids faible reprend. Cette méthode de réinitialisation et de débordement est répétée pour chaque chiffre significatif. Le comptage se déroule comme suit :

000, 001, 002, ... 007, 008, 009, (le chiffre le plus à droite est remis à zéro et le chiffre à sa gauche est incrémenté)
0 1 0, 011, 012, ...
   ...
090, 091, 092, ... 097, 098, 099, (les deux chiffres les plus à droite sont remis à zéro et le chiffre suivant est incrémenté)
1 00, 101, 102, ...

Comptage binaire

Ce compteur montre comment compter en binaire à partir des nombres zéro à trente et un.
Une astuce pour deviner un nombre à partir des cartes sur lesquelles il est imprimé utilise les bits de la représentation binaire du nombre. Dans le fichier SVG, cliquez sur une carte pour la basculer

Le comptage binaire suit la même procédure, sauf que seuls les deux symboles 0 et 1 sont disponibles. Ainsi, lorsqu'un chiffre atteint 1 en binaire, un incrément le remet à 0 mais provoque également un incrément du chiffre suivant vers la gauche :

0000,
000 1 , (le chiffre le plus à droite recommence et le chiffre suivant est incrémenté)
00 1 0, 0011 (les deux chiffres les plus à droite recommencent et le chiffre suivant est incrémenté)
0 1 00, 0101, 0110, 0111, (les trois chiffres les plus à droite recommencent et le chiffre suivant est incrémenté)
1 000, 1001, 1010, 1011, 1100, 1101, 1110, 1111...

Dans le système binaire, chaque chiffre représente une puissance croissante de 2, le chiffre le plus à droite représentant 2 0 , le suivant représentant 2 1 , puis 2 2 , et ainsi de suite. La valeur d'un nombre binaire est la somme des puissances de 2 représentées par chaque chiffre "1". Par exemple, le nombre binaire 100101 est converti au format décimal comme suit :

100101 2 = [ ( 1 ) × 2 5 ] + [ ( 0 ) × 2 4 ] + [ ( 0 ) × 2 3 ] + [ ( 1 ) × 2 2 ] + [ ( 0 ) × 2 1 ] + [ ( 1 ) × 2 0 ]
100101 2 = [ 1 × 32 ] + [ 0 × 16 ] + [ 0 × 8 ] + [ 1 × 4 ] + [ 0 × 2 ] + [ 1 × 1 ]
100101 2 = 37 10

Fractions

Les fractions en arithmétique binaire ne se terminent que si 2 est le seul facteur premier du dénominateur . En conséquence, 1/10 n'a pas de représentation binaire finie ( 10 a des facteurs premiers 2 et 5 ). Cela fait que 10 × 0,1 n'est pas exactement égal à 1 en arithmétique à virgule flottante . Par exemple, pour interpréter l'expression binaire pour 1/3 = .010101..., cela signifie : 1/3 = 0 × 2 −1 + 1 × 2 −2 + 0 × 2 −3 + 1 × 2 −4 + ... = 0,3125 + ... Une valeur exacte ne peut pas être trouvée avec une somme d'un nombre fini de puissances inverses de deux, les zéros et les uns dans la représentation binaire de 1/3 alternent pour toujours.

Fraction Décimal Binaire Approximation fractionnaire
1/1 1  ou  0,999... 1  ou  0,111... 1/2 + 1/4 + 1/8...
1/2 0,5  ou  0,4999... 0,1  ou  0,0111... 1/4 + 1/8 + 1/16 . . .
1/3 0,333... 0.010101... 1/4 + 1/16 + 1/64 . . .
1/4 0,25  ou  0,24999... 0,01  ou  0,00111... 1/8 + 1/16 + 1/32 . . .
1/5 0,2  ou  0,1999... 0,00110011... 1/8 + 1/16 + 1/128 . . .
1/6 0,1666... 0,0010101... 1/8 + 1/32 + 1/128 . . .
1/7 0.142857142857... 0,001001... 1/8 + 1/64 + 1/512 . . .
1/8 0,125  ou  0,124999... 0,001  ou  0,000111... 1/16 + 1/32 + 1/64 . . .
1/9 0,111... 0.000111000111... 1/16 + 1/32 + 1/64 . . .
1/10 0,1  ou  0,0999... 0,000110011... 1/16 + 1/32 + 1/256 . . .
1/11 0,090909... 0.00010111010001011101... 1/16 + 1/64 + 1/128 . . .
1/12 0,08333... 0.00010101... 1/16 + 1/64 + 1/256 . . .
1/13 0,076923076923... 0.000100111011000100111011... 1/16 + 1/128 + 1/256 . . .
1/14 0,0714285714285... 0,00001001001... 1/16 + 1/128 + 1/1024 . . .
1/15 0,0666... 0,0001001... 1/16 + 1/256 . . .
1/16 0,0625  ou  0,0624999... 0,0001  ou  0,0000111... 1/32 + 1/64 + 1/128 . . .

Arithmétique binaire

L'arithmétique en binaire ressemble beaucoup à l'arithmétique dans d'autres systèmes numériques. L'addition, la soustraction, la multiplication et la division peuvent être effectuées sur des nombres binaires.

Une addition

Le schéma de circuit d'un demi-additionneur binaire , qui ajoute deux bits ensemble, produisant des bits de somme et de retenue

L'opération arithmétique la plus simple en binaire est l'addition. L'ajout de deux nombres binaires à un chiffre est relativement simple, en utilisant une forme de transport :

0 + 0 → 0
0 + 1 → 1
1 + 0 → 1
1 + 1 → 0, porter 1 (car 1 + 1 = 2 = 0 + (1 × 2 1 ) )

L'ajout de deux chiffres "1" produit un chiffre "0", tandis que 1 devra être ajouté à la colonne suivante. Ceci est similaire à ce qui se passe en décimal lorsque certains nombres à un chiffre sont additionnés ; si le résultat est égal ou supérieur à la valeur de la base (10), le chiffre de gauche est incrémenté :

5 + 5 → 0, porter 1 (puisque 5 + 5 = 10 = 0 + (1 × 10 1 ) )
7 + 9 → 6, porte 1 (puisque 7 + 9 = 16 = 6 + (1 × 10 1 ) )

C'est ce qu'on appelle le portage . Lorsque le résultat d'une addition dépasse la valeur d'un chiffre, la procédure consiste à « porter » le montant excédentaire divisé par la base (c'est-à-dire 10/10) vers la gauche, en l'ajoutant à la valeur de position suivante. C'est correct puisque la position suivante a un poids qui est supérieur d'un facteur égal à la base. Le portage fonctionne de la même manière en binaire :

  1 1 1 1 1    (carried digits)
    0 1 1 0 1
+   1 0 1 1 1
-------------
= 1 0 0 1 0 0 = 36

Dans cet exemple, deux chiffres sont additionnés : 01101 2 (13 10 ) et 10111 2 (23 10 ). La ligne du haut montre les bits de retenue utilisés. En commençant dans la colonne la plus à droite, 1 + 1 = 10 2 . Le 1 est porté à gauche et le 0 est écrit en bas de la colonne la plus à droite. La deuxième colonne en partant de la droite est ajoutée : 1 + 0 + 1 = 10 2 à nouveau ; le 1 est porté, et 0 est écrit en bas. La troisième colonne : 1 + 1 + 1 = 11 2 . Cette fois, un 1 est porté, et un 1 est écrit dans la rangée du bas. En procédant ainsi, on obtient la réponse finale 100100 2 (36 décimal).

Lorsque les ordinateurs doivent additionner deux nombres, la règle suivante : x xou y = (x + y) mod 2 pour n'importe quels deux bits x et y permet également un calcul très rapide.

Méthode de portage longue

Une simplification pour de nombreux problèmes d'addition binaire est la méthode Long Carry ou méthode Brookhouse d'addition binaire . Cette méthode est généralement utile dans toute addition binaire dans laquelle l'un des nombres contient une longue "chaîne" de uns. Il est basé sur la prémisse simple que dans le système binaire, lorsqu'on lui donne une "chaîne" de chiffres composée entièrement de n uns (où n est une longueur entière), l'ajout de 1 donnera le nombre 1 suivi d'une chaîne de n zéros . Ce concept suit, logiquement, tout comme dans le système décimal, où l'ajout de 1 à une chaîne de n 9 se traduira par le nombre 1 suivi d'une chaîne de n 0 :

     Binary                        Decimal
    1 1 1 1 1     likewise        9 9 9 9 9
 +          1                  +          1
  ———————————                   ———————————
  1 0 0 0 0 0                   1 0 0 0 0 0

De telles chaînes longues sont assez courantes dans le système binaire. À partir de là, on constate que de grands nombres binaires peuvent être ajoutés en deux étapes simples, sans opérations de report excessives. Dans l'exemple suivant, deux chiffres sont additionnés : 1 1 1 0 1 1 1 1 1 0 2 (958 10 ) et 1 0 1 0 1 1 0 0 1 1 2 (691 10 ), en utilisant la méthode de report traditionnelle sur à gauche, et la méthode de longue portée à droite :

Traditional Carry Method                       Long Carry Method
                                vs.
  1 1 1   1 1 1 1 1      (carried digits)   1 ←     1 ←            carry the 1 until it is one digit past the "string" below
    1 1 1 0 1 1 1 1 1 0                       1 1 1 0 1 1 1 1 1 0  cross out the "string",
+   1 0 1 0 1 1 0 0 1 1                   +   1 0 1 0 1 1 0 0 1 1  and cross out the digit that was added to it
———————————————————————                    ——————————————————————
= 1 1 0 0 1 1 1 0 0 0 1                     1 1 0 0 1 1 1 0 0 0 1

La ligne du haut montre les bits de retenue utilisés. Au lieu du report standard d'une colonne à l'autre, le « 1 » de rang le plus bas avec un « 1 » dans la valeur de position correspondante en dessous peut être ajouté et un « 1 » peut être porté à un chiffre après la fin de la séries. Les numéros "utilisés" doivent être barrés, car ils sont déjà ajoutés. D'autres chaînes longues peuvent également être annulées en utilisant la même technique. Ensuite, additionnez simplement les chiffres restants normalement. Procéder de cette manière donne la réponse finale de 1 1 0 0 1 1 1 0 0 0 1 2 (1649 10 ). Dans notre exemple simple utilisant de petits nombres, la méthode de portage traditionnelle nécessitait huit opérations de portage, alors que la méthode de portage long n'en nécessitait que deux, ce qui représente une réduction substantielle de l'effort.

Tableau d'addition

0 1
0 0 1
1 1 dix

La table d'addition binaire est similaire, mais pas identique, à la table de vérité de l' opération de disjonction logique . La différence est que , tandis que .

Soustraction

La soustraction fonctionne à peu près de la même manière :

0 − 0 → 0
0 − 1 → 1, emprunter 1
1 − 0 → 1
1 − 1 → 0

Soustraire un chiffre "1" d'un chiffre "0" produit le chiffre "1", tandis que 1 devra être soustrait de la colonne suivante. C'est ce qu'on appelle l' emprunt . Le principe est le même que pour le portage. Lorsque le résultat d'une soustraction est inférieur à 0, la plus petite valeur possible d'un chiffre, la procédure consiste à « emprunter » le déficit divisé par la base (c'est-à-dire 10/10) à partir de la gauche, en le soustrayant à la position suivante. valeur.

    *   * * *   (starred columns are borrowed from)
  1 1 0 1 1 1 0
−     1 0 1 1 1
----------------
= 1 0 1 0 1 1 1
  *             (starred columns are borrowed from)
  1 0 1 1 1 1 1
-   1 0 1 0 1 1
----------------
= 0 1 1 0 1 0 0

Soustraire un nombre positif équivaut à ajouter un nombre négatif de valeur absolue égale . Les ordinateurs utilisent des représentations de nombres signés pour gérer les nombres négatifs, le plus souvent la notation complémentaire à deux . De telles représentations éliminent le besoin d'une opération de « soustraction » distincte. En utilisant la notation complémentaire à deux, la soustraction peut être résumée par la formule suivante :

A − B = A + pas B + 1

Multiplication

La multiplication en binaire est similaire à son homologue décimal. Deux nombres A et B peuvent être multipliés par des produits partiels : pour chaque chiffre de B , le produit de ce chiffre de A est calculé et écrit sur une nouvelle ligne, décalé vers la gauche de sorte que son chiffre le plus à droite s'aligne avec le chiffre de B qui a été utilisé. La somme de tous ces produits partiels donne le résultat final.

Puisqu'il n'y a que deux chiffres en binaire, il n'y a que deux résultats possibles de chaque multiplication partielle :

  • Si le chiffre dans B est 0, le produit partiel est également 0
  • Si le chiffre dans B est 1, le produit partiel est égal à A

Par exemple, les nombres binaires 1011 et 1010 sont multipliés comme suit :

           1 0 1 1   (A)
         × 1 0 1 0   (B)
         ---------
           0 0 0 0   ← Corresponds to the rightmost 'zero' in B
   +     1 0 1 1     ← Corresponds to the next 'one' in B
   +   0 0 0 0
   + 1 0 1 1
   ---------------
   = 1 1 0 1 1 1 0

Les nombres binaires peuvent également être multipliés par des bits après un point binaire :

               1 0 1 . 1 0 1     A (5.625 in decimal)
             × 1 1 0 . 0 1       B (6.25 in decimal)
             -------------------
                   1 . 0 1 1 0 1   ← Corresponds to a 'one' in B
     +           0 0 . 0 0 0 0     ← Corresponds to a 'zero' in B
     +         0 0 0 . 0 0 0
     +       1 0 1 1 . 0 1
     +     1 0 1 1 0 . 1
     ---------------------------
     =   1 0 0 0 1 1 . 0 0 1 0 1 (35.15625 in decimal)

Voir aussi l'algorithme de multiplication de Booth .

Table de multiplication

0 1
0 0 0
1 0 1

La table de multiplication binaire est la même que la table de vérité de l' opération de conjonction logique .

Division

La division longue en binaire est à nouveau similaire à son homologue décimal.

Dans l'exemple ci-dessous, le diviseur est 101 2 , soit 5 en décimal, tandis que le dividende est 11011 2 , soit 27 en décimal. La procédure est la même que celle de la division longue décimale ; ici, le diviseur 101 2 entre une fois dans les trois premiers chiffres 110 2 du dividende, donc un "1" est écrit sur la ligne du haut. Ce résultat est multiplié par le diviseur et soustrait des trois premiers chiffres du dividende ; le chiffre suivant (un "1") est inclus pour obtenir une nouvelle séquence à trois chiffres :

              1
        ___________
1 0 1   ) 1 1 0 1 1
        − 1 0 1
          -----
          0 0 1

La procédure est ensuite répétée avec la nouvelle séquence, en continuant jusqu'à ce que les chiffres du dividende soient épuisés :

             1 0 1
       ___________
1 0 1  ) 1 1 0 1 1
       − 1 0 1
         -----
             1 1 1
         −   1 0 1
             -----
             0 1 0

Ainsi, le quotient de 11011 2 divisé par 101 2 est de 101 2 , comme indiqué sur la ligne du haut, tandis que le reste, indiqué sur la ligne du bas, est de 10 2 . En décimal, cela correspond au fait que 27 divisé par 5 fait 5, avec un reste de 2.

Outre la division longue, on peut également concevoir la procédure de manière à permettre une sur-soustraction du reste partiel à chaque itération, conduisant ainsi à des méthodes alternatives moins systématiques, mais par conséquent plus flexibles.

Racine carrée

Le processus de prise d'une racine carrée binaire chiffre par chiffre est le même que pour une racine carrée décimale et est expliqué ici . Un exemple est :

             1 0 0 1
            ---------
           √ 1010001
             1
            ---------
      101     01 
               0
             --------
      1001     100
                 0
             --------
      10001    10001
               10001
              -------
                   0

Opérations au niveau du bit

Bien qu'elles ne soient pas directement liées à l'interprétation numérique des symboles binaires, les séquences de bits peuvent être manipulées à l' aide d' opérateurs logiques booléens . Lorsqu'une chaîne de symboles binaires est manipulée de cette manière, cela s'appelle une opération au niveau du bit ; les opérateurs logiques AND , OR et XOR peuvent être exécutés sur les bits correspondants de deux chiffres binaires fournis en entrée. L' opération logique NON peut être effectuée sur des bits individuels dans un seul chiffre binaire fourni en entrée. Parfois, de telles opérations peuvent être utilisées comme raccourcis arithmétiques et peuvent également présenter d'autres avantages en termes de calcul. Par exemple, un décalage arithmétique vers la gauche d'un nombre binaire est l'équivalent d'une multiplication par une puissance (positive, intégrale) de 2.

Conversion vers et depuis d'autres systèmes numériques

Décimal

La conversion de (357) 10 en notation binaire donne (101100101)

Pour convertir un entier en base 10 en son équivalent en base 2 (binaire), le nombre est divisé par deux . Le reste est le bit le moins significatif . Le quotient est à nouveau divisé par deux ; son reste devient le bit le moins significatif suivant. Ce processus se répète jusqu'à ce qu'un quotient de un soit atteint. La séquence de restes (y compris le quotient final de un) forme la valeur binaire, car chaque reste doit être soit zéro, soit un lors de la division par deux. Par exemple, (357) 10 est exprimé sous la forme (101100101) 2.

La conversion de base-2 en base-10 inverse simplement l'algorithme précédent. Les bits du nombre binaire sont utilisés un par un, en commençant par le bit le plus significatif (le plus à gauche). En commençant par la valeur 0, la valeur précédente est doublée et le bit suivant est ensuite ajouté pour produire la valeur suivante. Cela peut être organisé dans un tableau à plusieurs colonnes. Par exemple, pour convertir 10010101101 2 en décimal :

Valeur antérieure × 2 + Morceau suivant Valeur suivante
0 × 2 + 1 = 1
1 × 2 + 0 = 2
2 × 2 + 0 = 4
4 × 2 + 1 = 9
9 × 2 + 0 = 18
18 × 2 + 1 = 37
37 × 2 + 0 = 74
74 × 2 + 1 = 149
149 × 2 + 1 = 299
299 × 2 + 0 = 598
598 × 2 + 1 = 1197

Le résultat est 1197 10 . La première valeur antérieure de 0 est simplement une valeur décimale initiale. Cette méthode est une application du schéma de Horner .

Binaire  1 0 0 1 0 1 0 1 1 0 1
Décimal  1×2 10 + 0×2 9 + 0×2 8 + 1×2 7 + 0×2 6 + 1×2 5 + 0×2 4 + 1×2 3 + 1×2 2 + 0×2 1 + 1×2 0 = 1197

Les parties fractionnaires d'un nombre sont converties avec des méthodes similaires. Ils sont à nouveau basés sur l'équivalence du décalage avec le doublement ou la réduction de moitié.

Dans un nombre binaire fractionnaire tel que 0,11010110101 2 , le premier chiffre est , le deuxième , etc. Donc, s'il y a un 1 à la première place après la virgule, alors le nombre est au moins , et vice versa. Doubler ce nombre est au moins 1. Cela suggère l'algorithme : doublez à plusieurs reprises le nombre à convertir, enregistrez si le résultat est au moins 1, puis jetez la partie entière.

Par exemple, 10 , en binaire, est :

Conversion Résultat
0.
0.0
0,01
0,010
0,0101

Ainsi, la fraction décimale répétée 0. 3 ... est équivalente à la fraction binaire répétée 0. 01 ... .

Ou par exemple, 0,1 10 , en binaire, vaut :

Conversion Résultat
0,1 0.
0,1 × 2 = 0,2 < 1 0.0
0,2 × 2 = 0,4 < 1 0,00
0,4 × 2 = 0,8 < 1 0,000
0,8 × 2 = 1,6 × 1 0,0001
0,6 × 2 = 1,2 × 1 0.00011
0,2 × 2 = 0,4 < 1 0,000110
0,4 × 2 = 0,8 < 1 0,0001100
0,8 × 2 = 1,6 × 1 0,00011001
0,6 × 2 = 1,2 × 1 0,000110011
0,2 × 2 = 0,4 < 1 0,0001100110

C'est aussi une fraction binaire répétitive 0.0 0011 ... . Il peut être surprenant que les fractions décimales terminales puissent avoir des développements répétés en binaire. C'est pour cette raison que beaucoup sont surpris de découvrir que 0,1 + ... + 0,1, (10 additions) diffère de 1 en arithmétique à virgule flottante . En fait, les seules fractions binaires avec des développements terminaux sont de la forme d'un entier divisé par une puissance de 2, ce qui n'est pas 1/10.

La conversion finale est des fractions binaires en fractions décimales. La seule difficulté survient avec la répétition de fractions, mais sinon la méthode consiste à décaler la fraction en un entier, à la convertir comme ci-dessus, puis à diviser par la puissance appropriée de deux dans la base décimale. Par exemple:

Une autre façon de convertir du binaire en décimal, souvent plus rapide pour une personne familière avec l' hexadécimal , consiste à le faire indirectement, d'abord en convertissant ( en binaire) en ( en hexadécimal) puis en convertissant ( en hexadécimal) en ( en décimal).

Pour les très grands nombres, ces méthodes simples sont inefficaces car elles effectuent un grand nombre de multiplications ou de divisions où un opérande est très grand. Un algorithme simple diviser pour régner est plus efficace asymptotiquement : étant donné un nombre binaire, il est divisé par 10 k , où k est choisi de sorte que le quotient soit à peu près égal au reste ; puis chacune de ces pièces est convertie en décimal et les deux sont concaténées . Étant donné un nombre décimal, il peut être divisé en deux morceaux d'environ la même taille, chacun étant converti en binaire, après quoi le premier morceau converti est multiplié par 10 k et ajouté au deuxième morceau converti, où k est le nombre de chiffres décimaux dans la seconde partie la moins significative avant la conversion.

Hexadécimal

0 hexagone = 0 déc = 0 octobre 0 0 0 0
1 hexagone = 1 déc. = 1 octobre 0 0 0 1
2 hexagones = 2 déc = 2 octobre 0 0 1 0
3 hexagones = 3 déc = 3 octobre 0 0 1 1
4 hexagones = 4 déc = 4 octobre 0 1 0 0
5 hexagones = 5 déc = 5 octobre 0 1 0 1
6 hexagones = 6 déc. = 6 octobre 0 1 1 0
7 hexagones = 7 déc = 7 octobre 0 1 1 1
8 hexagones = 8 déc. = 10 octobre 1 0 0 0
9 hexagones = 9 déc. = 11 octobre 1 0 0 1
Un hexagone = 10 déc = 12 octobre 1 0 1 0
B hexagone = 11 déc. = 13 octobre 1 0 1 1
C hex = 12 déc = 14 octobre 1 1 0 0
D hex = 13 déc. = 15 octobre 1 1 0 1
E hexagone = 14 déc = 16 octobre 1 1 1 0
F hex = 15 déc. = 17 octobre 1 1 1 1

Le binaire peut être converti en hexadécimal plus facilement. En effet, la base du système hexadécimal (16) est une puissance de la base du système binaire (2). Plus précisément, 16 = 2 4 , il faut donc quatre chiffres binaires pour représenter un chiffre hexadécimal, comme indiqué dans le tableau adjacent.

Pour convertir un nombre hexadécimal en son équivalent binaire, substituez simplement les chiffres binaires correspondants :

3A 16 = 0011 1010 2
E7 16 = 1110 0111 2

Pour convertir un nombre binaire en son équivalent hexadécimal, divisez-le en groupes de quatre bits. Si le nombre de bits n'est pas un multiple de quatre, insérez simplement 0 bits supplémentaires à gauche (appelé padding ). Par exemple:

1010010 2 = 0101 0010 groupé avec rembourrage = 52 16
11011101 2 = 1101 1101 groupé = DD 16

Pour convertir un nombre hexadécimal en son équivalent décimal, multipliez l'équivalent décimal de chaque chiffre hexadécimal par la puissance correspondante de 16 et ajoutez les valeurs résultantes :

C0E7 16 = (12 × 16 3 ) + (0 × 16 2 ) + (14 × 16 1 ) + (7 × 16 0 ) = (12 × 4096) + (0 × 256) + (14 × 16) + ( 7 × 1) = 49 383 10

Octal

Le binaire est également facilement converti en système de numération octal , car octal utilise une base de 8, qui est une puissance de deux (à savoir, 2 3 , il faut donc exactement trois chiffres binaires pour représenter un chiffre octal). La correspondance entre les chiffres octaux et binaires est la même que pour les huit premiers chiffres de l' hexadécimal dans le tableau ci-dessus. Le binaire 000 équivaut au chiffre octal 0, le binaire 111 équivaut au octal 7, et ainsi de suite.

Octal Binaire
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

La conversion de l'octal en binaire se fait de la même manière que pour l' hexadécimal :

65 8 = 110 101 2
17 8 = 001 111 2

Et du binaire à l'octal :

101100 2 = 101 100 2 groupés = 54 8
10011 2 = 010 011 2 groupé avec rembourrage = 23 8

Et de l'octal au décimal :

65 8 = (6 × 8 1 ) + (5 × 8 0 ) = (6 × 8) + (5 × 1) = 53 10
127 8 = (1 × 8 2 ) + (2 × 8 1 ) + (7 × 8 0 ) = (1 × 64) + (2 × 8) + (7 × 1) = 87 10

Représenter des nombres réels

Les non-entiers peuvent être représentés en utilisant des puissances négatives, qui sont séparées des autres chiffres au moyen d'un point de base (appelé point décimal dans le système décimal). Par exemple, le nombre binaire 11.01 2 signifie :

1 × 2 1 (1 × 2 = 2 ) plus
1 × 2 0 (1 × 1 = 1 ) plus
0 × 2 −1 (0 × une / 2 = 0 ) plus
1 × 2 −2 (1 x 1 / quatre = 0,25 )

Pour un total de 3,25 décimal.

Tous les nombres rationnels dyadiques ont un nombre binaire terminal - la représentation binaire a un nombre fini de termes après le point de base. D'autres nombres rationnels ont une représentation binaire, mais au lieu de se terminer, ils se répètent, avec une séquence finie de chiffres se répétant indéfiniment. Par exemple

Le phénomène selon lequel la représentation binaire de tout rationnel se termine ou se répète se produit également dans d'autres systèmes de numération basés sur la base. Voir, par exemple, l'explication en décimal . Une autre similitude est l'existence de représentations alternatives pour toute représentation terminale, en s'appuyant sur le fait que 0,111111... est la somme de la série géométrique 2 −1 + 2 −2 + 2 −3 + ... qui est 1.

Les nombres binaires qui ne se terminent ni ne se reproduisent représentent des nombres irrationnels . Par exemple,

  • 0.10100100010000100000100... a un modèle, mais ce n'est pas un modèle récurrent de longueur fixe, donc le nombre est irrationnel
  • 1.0110101000001001111001100110011111110... est la représentation binaire de , la racine carrée de 2 , un autre irrationnel. Il n'a pas de modèle discernable.

Voir également

Les références

Lectures complémentaires

  • Sanchez, Julio; Canton, Maria P. (2007). Programmation du microcontrôleur : la puce PIC . Boca Raton, Floride : CRC Press. p. 37. ISBN 978-0-8493-7189-9.
  • Redmond, Geoffroy ; Hon, Tze-Ki (2014). Enseigner le I Ching . Presses de l'Université d'Oxford. ISBN 978-0-19-976681-9.

Liens externes