Comparer deux nombres représentés en complément à 2

Version imprimable

01/07/2021, 22h46
Fatouchka

Comparer deux nombres représentés en complément à 2

Bonjour à tous,

Comment faire pour comparer 2 nombres représentés en compléments à 2 ?

J'ai mis ceci mais pas sûre que ce soit suffisant :

1. Comparer leur bit fort => Le nombre commençant par 0 sera plus grand

2. Ensuite il faut comparer les bits un à un en partant de la gauche, le 1 sera supérieur au 0.

Merci pour votre aide !
02/07/2021, 00h01
f-leb

Bonsoir,

Ou alors : A > B <==> A - B > 0

Tu fais la soustraction A + (-B) et tu regardes le signe du résultat (son bit de poids fort).
02/07/2021, 14h14
Guesset

Nombre signé déguisés

Bonjour,

Les entiers signés utilisent déjà le complément à 2. Par exemple en 32 bits, -a correspondra à la valeur non signée 2³² - a.

Bonne nouvelle (même si elle est très ancienne), les CPU traitent directement les entiers signés donc en complément à 2. Alors pour comparer deux nombres il suffit d'écrire a < b ou de caster (c'est à dire forcer le type de) l'expression int(a) < int(b) si les variables a et b ont été initialement déclarées comme non signées.

Salutations
03/07/2021, 19h20
Fatouchka

Citation:

Envoyé par f-leb

Bonsoir,

Ou alors : A > B <==> A - B > 0

Tu fais la soustraction A + (-B) et tu regardes le signe du résultat (son bit de poids fort).

Merci beaucoup pour ton aide je comprends mieux !

Citation:

Envoyé par Guesset

Bonjour,

Les entiers signés utilisent déjà le complément à 2. Par exemple en 32 bits, -a correspondra à la valeur non signée 2³² - a.

Bonne nouvelle (même si elle est très ancienne), les CPU traitent directement les entiers signés donc en complément à 2. Alors pour comparer deux nombres il suffit d'écrire a < b ou de caster (c'est à dire forcer le type de) l'expression int(a) < int(b) si les variables a et b ont été initialement déclarées comme non signées.

Salutations

Merci beaucoup pour ton aide !

Je voudrais faire un programme en python qui demande de saisir deux nombres en complément à 2 et les comparer.

Mon code est-il correct ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 print ('Veuillez saisir deux nombres en code binaire sur 4 bits.') print ('Rappel les nombres ne doivent contenir que des 0 ou des 1.') a= int(input('Veuillez saisir votre premier nombre') b= int(input('Veuillez saisir votre second nombre') def comparaison(a, b): if (a == b): # A = B return 0 elif (a[0] == 1 and b[0] == 0): # A < 0 et B > 0 return -1 elif (a[0] == 0 and b[0] == 1): # A > 0 et B < 0 return 1 else: for i in xrange(1, 8): # Pour i de 1 à 7 if (a[i] > b[i]): return 1 elif (a[i] < b[i]): return -1

03/07/2021, 19h58
AbsoluteLogic
Salut,

Tu sembles utiliser tes variables a et b comme des tableaux de bits. Dans ce cas, tu devrais plutôt les initialiser avec le code ci-dessous (syntaxe de "compréhension de liste") :

Code:

a = [int(c) for c in input(...)]

Aussi, je ne vois pas la logique de faire le test "a == b". Si tu programme cette fonction, c'est logiquement que tu t'interdis d'utiliser ces opérateurs entre entier. La solution consiste juste à retourner 0 à la fin de ta fonction si rien n'a été retourné avant.

Enfin, je reprends le sujet de base en disant que le complément à 2, c'est comme des entiers normaux, mais juste dont le 1er bit a un poids négatif. Ainsi, tu peux retirer tes conditions initiales, et dans ta boucle, tu peux faire:
Code:

1 2 3 4 5 for i in xrange(0, 8): if (a[i] > b[i]): return 1 if i >= 1 else -1 elif (a[i] < b[i]): return -1 if i >= 1 else 1
Tu sembles utiliser Python 2. Je ne connais que Python 3, donc j'espère que les syntaxes que j'ai utilisées fonctionnent.

PS : Tu te contredis : c'est sur 4 bits ou sur 8 bits ?
04/07/2021, 11h38
Fatouchka

Hello Je te remercie pour ta réponse

mais je ne comprends pas ton code
il faut d'abord tester le bit de signe ensuite les autres bit mais si on boucle sur le premier on ne résoud pas le problème ?
04/07/2021, 12h22
AbsoluteLogic
Juste pour clarifier, à part pour le problème d'initialisation des a et b, ton code fonctionne.

Ensuite, je te proposais une "factorisation du code". En effet, en complément à 2 sur 8 bits, les bits auront les poids suivant : -256 128 64 32 16 8 4 2 1. Pour une comparaison, tu dois comparer tous les bits en partant du plus fort jusqu'à plus faible. Le bit de signe a un poids de "-256", qui est bien le plus fort. Ainsi, tu peux l'inclure dans ta boucle. C'est juste que s'ils diffèrent (cas de i == 0 dans ta boucle), puisque leur poids est négatif, il te faut retourner le contraire dans ce cas.

Mon code est équivalent au tien, puisque
Code:

1 2 3 4 if (a[0] == 1 and b[0] == 0): # A < 0 et B > 0 return -1 elif (a[0] == 0 and b[0] == 1): # A > 0 et B < 0 return 1
peut être remplacé par
Code:

1 2 3 4 if (a[0] > b[0]): # A < 0 et B > 0 return -1 elif (a[0] < b[0]): # A > 0 et B < 0 return 1
qui peut être inséré dans ta boucle en inversant le résultat dans ce cas.

J'ai essayé ceci mais je dois saisir mes nombres comme un tableau.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ddef comparaison(a, b):
    if (a == b):  # A = B
        return 0
    elif (a[0] == 1 and b[0] == 0):  # A < 0 et B > 0
        return -1
    elif (a[0] == 0 and b[0] == 1):  # A > 0 et B < 0
        return 1
    else:
        for i in xrange(1, 8):  # Pour i de 1 à 7
            if (a[i] > b[i]):
                return 1
            elif (a[i] < b[i]):
                return -1
 
 
a = [1, 1, 0, 1, 0, 0, 1, 1]
b = [0, 1, 0, 1, 0, 0, 1, 1]
 
if comparaison(a,b)==-1:
    print('B est plus grand que A')
elif comparaison(a,b)==1:
    print('A est plus grand que B')
else:
    print ('Les nombres sont égaux')

J'aimerais optimiser ce code :
1. pouvoir saisir directement les nombres (j'ai essayé avec a=list(input('saisir votre premier nombre : ')) mais le code bug...
2. Pas sûre que mon affichage soit optimal non plus

06/07/2021, 00h33
AbsoluteLogic

Citation:

pouvoir saisir directement les nombres (j'ai essayé avec a=list(input('saisir votre premier nombre : ')) mais le code bug

Pourquoi n'utilises-tu pas l'expression que je t'ai donné avant ?

Code:

a = [int(c) for c in input(...)]

Ton code lit le texte en caractères, il faut le convertir en entiers (avec int par exemple).

Citation:

mais le code bug

Ne jamais dire qu'un code bug sans dire l'erreur produite.

Citation:

Pas sûre que mon affichage soit optimal non plus

Si tu veux dire à cause du double appel à la fonction, c'est là que les variables sont utiles : tu stockes le résultat pour le réutiliser plusieurs fois ensuite.

Bon, par contre, c'est plus un problème de Python que d'algorithmie maintenant. Il y a des cours qui sont là pour ça, et si t'as des questions précises, Google ou le forum Python...
07/07/2021, 10h02
Fatouchka

Merci beaucoup pour vos réponses cela m'a vraiment aidée !

Petite question : trouver les deux valeurs pour lesquelles le complément à deux ne change pas le bit de signe de la représentation d’un nombre.

Je pense que c'est 0 et -128
car nous avons 0 : 00000000
et -128 : 10000000
Mais je ne sais pas comment expliquer cela de manière logique (j'ai fait intuitivemement).
07/07/2021, 19h36
Guesset

Invariant
Bonjour,

Oui, 0 et -128 sont les invariants de la complémentarité à 2 pour un octet.

Pour un nombre p non signé, son complément à 2, également non signé, est n = 2⁸ - p modulo 256 pour un octet (2¹⁶ - p modulo 2¹⁶ pour un word, , 2³² - p modulo 2³² pour un 32 bits...).

Invariant => p = 2⁸ - p modulo 256 (le modulo oblige à rester dans la taille du type d'entier choisi).
- Si 2⁸ - p < 256 alors l'expression est équivalente à p = 2⁸ - p soit 2p = 2⁸ soit p = 2⁷ = 128. (par convention on écrit -128 car le bit de poids fort est à 1)
- Si 2⁸ - p >= 256 c'est équivalent à 2⁸ - 256 >= p soit p <= 0, mais p est non signé donc p = 0. Vérifions que 0 est solution : 2⁸ - 0 modulo 256 = 256 modulo 256 = 0. CQFD
La valeur -128 (et ses sœurs) est assez dangereuse à utiliser :
- Elle peut être considérée comme un 0 si on considère n = -n.
- Elle peut être considérée comme +128 puisque -128 - 1 = 127
Invariant du bit de signe
Complément à 2 de p est n = ~p + 1. ~p est le complément à 1 (inversion des bits), il a donc un bit de signe opposé à celui de p. Pour à nouveau l'inverser et revenir à la valeur initiale, il faut que le +1 provoque une retenue sur ce bit ce qui n'est possible que si tous les autres bits de ~p sont à 1 (soit 2⁷ -1) ce qui revient à dire que les 7 premiers bits de p sont à 0. Les solutions sont donc 0b00000000 et 0b10000000 soit 0 et -128.

Salutations