Rappel :

 

En base b, chaque chiffre xn d’un nombre entier nb à N chiffres possède un rang n (à partir de 0 en commençant par la droite) tel que :

 

nb = xN-1 . bN-1+ … +xn . bn + … + x1 . b1 + x0 . b0

 

On a bien 1638 = 1 x 103 + 6 x 102 + 3 x 101 + 8 x 100

 

6 est le chiffre de rang 2, 8 de rang 0

 

 

Une addition en base 10 se pose de la manière suivante avec une retenue qui initialement vaut toujours 0 :

 

 

 

En commençant par le rang 0, on additionne les 2 chiffres de même rang et la retenue, si le total est supérieur à la base-1 (9 ici) on soustrait la base au total et la retenue est fixée à 1 sinon la retenue est fixée 0.

Dans l’exemple en base 10,

retenue=0

5 + 8 + 0 = 13

> 13 – 10 = 3 et retenue=1

> 9 + 4 + 1 = 14

> 14 – 10 =et retenue=1

> 4 + 3 + 1 = 8

> retenue=0

> 1 + 0 + 0 = 1

 

 

En binaire, le principe est le même : en commençant par le rang 0, on additionne les 2 chiffres de même rang et la retenue initialement égale à 0, si le total est supérieur à 1 (base-1 ici) on soustrait 2 au total et la retenue est fixée à 1 sinon la retenue est fixée 0. D’où :

 

 

 

 

 

On a donc en binaire 1011 + 111 = 10010

 

Pour créer des nombres binaires, nous allons créer des listes de 0 et 1.

1011 devient [1,0,1,1]

111 devient [0,1,1,1] car nous allons additionner les chiffres de 2 listes de taille identique.

 

Attention :

Le rang 0 du nombre binaire est le dernier rang de la liste mais nous pouvons parcourir une liste dans l’autre sens en utilisant des indices négatifs.

 

 

 

L’algorithme s’écrit donc pour les listes de 0 et 1 listBin1 et listBin2:

 

Entrèe : listes de 0 et 1 listBin1 et listBin2 de taille identique.

Traitement de addition_binaire :

initialiser retenue à 0 et size à la taille de listBin1

Pour i de 1 à size−1

somme prend la valeur listBin1[-(i+1)] + listBin2[-(i+1)] + retenue (on commence par la fin de la liste)

Si somme <= 1

listBin1[-(i+1)]=somme (on utilise une des liste pour stocker le résultat car les listes entrées sont de toute façon stockée ailleurs)

retenue=0

finSi

Sinon :

listBin1[-(i+1)]=somme-2

retenue=1

finSinon

FinPour

Si retenue=1

initialisation d’une lise L1 à [1]

ajout de listBin1 à la fin de L1

Sortie : L1

finSi

Sinon :

Sortie : listBin1

FinSinon

 

 

 

 

Ce qui donne en Python :

 


def addition_binaire(listBin1,listBin2):
	retenue=0
	size=len(listBin1)
	for i in range(size) :
		somme=listBin1[-(i+1)]+listBin2[-(i+1)]+retenue
		if somme <= 1 :
			listBin1[-(i+1)]=somme
			retenue=0
		else :
			listBin1[-(i+1)]=somme-2
			retenue=1
	if retenue==1:
		L1=[1]
		L1.extend(listBin1)
		return L1
	else:
		return listBin1

 

 

On peut créer une calculatrice où l’on considère que les 2 nombres sont des chaînes de caractères 0 et 1, pour cela on utilise en Python raw_input() à la place de input().

 

Une chaîne de caractère est une suite de caractère que l’on peut décomposer en une liste de caractères que l’on peut ensuite convertir en entier avec int() et avoir au final nos 2 listes d’entiers 0 et 1

 

Le résultat final, liste d’entiers 0 et 1, peut être converti en liste de caractères 0 et 1. Ces caractères 0 et 1 peuvent être réunis en une chaîne grâce à la méthode « join ». Il suffit d’écrire " ".join(la liste de caractère)

 

Il faut donc une fonction qui transforme les 2 chaînes de caractères en 2 listes d’entiers 0 et 1 de même taille, la fonction d’addition et une petite fonction pour transformer une liste d’entiers 0 et 1 en liste de caractères 0 et 1.

 

 



def creeListeEntierMemeTaille(chaineNb1,chaineNb2):
	lg1,lg2=len(chaineNb1),len(chaineNb2)
	Liste1,Liste2=[],[]
	for i in range(lg1):
		Liste1.append(int(chaineNb1[i]))
	for i in range(lg2):
		Liste2.append(int(chaineNb2[i]))	
	if lg2>lg1: 
		L1=[]	
		for i in range(lg2-lg1):
			L1.append(0)
		L1.extend(Liste1)
		L2=Liste2
	else:
		L2=[]	
		for i in range(lg1-lg2):
			L2.append(0)
		L2.extend(Liste2)
		L1=Liste1
	return L1,L2


def addition_binaire(listBin1,listBin2):
	retenue=0
	size=len(listBin1)
	for i in range(size) :
		somme=listBin1[-(i+1)]+listBin2[-(i+1)]+retenue
		if somme <= 1 :
			listBin1[-(i+1)]=somme
			retenue=0
		else :
			listBin1[-(i+1)]=somme-2
			retenue=1
	if retenue==1:
		L1=[1]
		L1.extend(listBin1)
		return L1
	else:
		return listBin1


def creeListeCaractere(listeEntier):
	listeCaract=[]
	for i in range(len(listeEntier)):
		listeCaract.append(str(listeEntier[i]))
	return listeCaract


chaine1 = raw_input("Nombre binaire 1 \n")
chaine2 = raw_input("\nNombre binaire 2 \n")

L3,L4=creeListeEntierMemeTaille(chaine1,chaine2)

print("\nL'addition en binaire donne : ")
L=addition_binaire(L3,L4)
#print(L)
ListCaract=creeListeCaractere(L)
#print(ch)
print("".join(ListCaract))

Free Joomla! template by L.THEME