Nombres négatifs en binaire
Jusqu’à présent, nous avons parlé des entiers positifs et de leur représentation dans nos machines. Pourtant, il nous arrive parfois d’avoir besoin de gérer des nombres négatifs. Comment ces nombres sont-ils représentés dans les ordinateurs ?
Nous avons vu que le nombre 1 est représenté par
0001 en binaire, le nombre 6 par 0110, etc. Par ailleurs, 0 est représenté par 0000, c’est-à-dire tous les bits à zéro. Une astuce simple pour stocker des nombres négatifs consiste à réserver un bit “spécial” qui indique si le nombre est négatif ou non. Ainsi, ce bit vaut 1 si le nombre est négatif et 0 sinon. C’est exactement la façon dont la plupart des ordinateurs gèrent les nombres négatifs. Ils réservent simplement un bit, tout à gauche dans la représentation binaire, qui est réglé à 1 si le nombre est négatif et à 0 s’il est positif.Il y a néanmoins plus que le simple fait de mettre le premier bit à 1. En représentation décimale (nos nombres habituels, comme 4, 5, 10, 311, etc.), les nombres positifs et négatifs s’annulent mutuellement. Ainsi, l’addition de 6 et -6 donne 0. Cette propriété doit également se maintenir en binaire. Donc, si nous additionnons 6 et -6 en binaire, nous devrions obtenir 0.
Imaginons que nous disposions de 4 bits pour représenter le nombre et d’un bit supplémentaire pour le signe, ce qui fait donc 5 bits au total. Ainsi, 6 serait représenté par
00110, tandis que 0 serait 00000. La représentation binaire de -6 doit être l’inverse de celle de 6 pour que leur somme donne 0. Sans trop anticiper, -6 est représenté par 11010. Dès lors, l’addition en binaire de 00110 et 11010 doit aboutir à 00000.Pour passer d’un nombre positif à un nombre négatif (et inversement) en binaire, on peut utiliser une astuce simple : on inverse tous les bits (tous les 0 deviennent 1 et tous les 1 deviennent 0) puis on ajoute 1 au résultat.
x = 6 # 00110
x = ~x + 1 # Inverse tous les bits et ajoute 1 => -6
x = ~x + 1 # Inverse tous les bits et ajoute 1 => 6
z = 0 # 00000
z = ~z + 1 # Inverse et +1 => 0
z = ~z + 1 # Inverse et +1 => 0
z = ~z # -1 (tous les bits à 1 dans la représentation binaire)
z = ~z # 0 (tous les bits à 0 dans la représentation binaire)Remarque : l’addition en binaire se fait de la même manière qu’en décimal, en procédant du chiffre le moins significatif vers le plus significatif, tout en gérant la retenue.
Selon le langage et l’implémentation, les ordinateurs peuvent stocker les nombres de façons différentes. Des langages comme C++ et Java proposent divers types permettant de représenter différentes plages de valeurs. Le type
int stocke un entier sur 32 bits : 31 bits pour la valeur et le bit de tête pour le signe ⇒ les valeurs possibles vont de -2,147,483,648 () à 2,147,483,647 (). Vous remarquerez que le maximum des valeurs positives est plus petit que celui des négatives d’une unité. Cela s’explique par le fait que les nombres positifs commencent avec un bit 0, et que le premier nombre qui commence par un bit 0 est 0 lui-même (tous les bits sont à 0).Challenge
Dans le pays magique du chiffre 7, tout est pensé pour tourner autour de ce nombre. Ainsi, dans ce royaume, les informaticiens ont élaboré un système qui stocke les nombres binaires en 77 bits (aussi bien positifs que négatifs).
Étant donné une chaîne de bits
b, vous devez calculer la valeur négative de ce nombre et la représenter en 77 bits.Entrée
L’entrée contient une seule ligne qui représente la chaîne de bits
b (1 ≤ |b| ≤ 77). Il peut s’agir d’un nombre positif ou négatif.Sortie
La sortie doit contenir une seule ligne représentant
-b sur 77 bits.Exemples
Entrée | Sortie |
1 | 11111111111111111111111111111111111111111111111111111111111111111111111111111 |
11111111111111111111111111111111111111111111111111111111111111111111111111111 | 00000000000000000000000000000000000000000000000000000000000000000000000000001 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB