binaire.py

Created on October 31, 2023
2.4 KB
Diverses fonctions relatives à la décomposition en binaire
# Les chiffres binaires sont dans le sens habituel: des bits de poids forts vers les bits de poids faibles (le dernier est l'unité, donnant la parité).

def somme0(chiffres):
  somme = 0
  log2 = len(chiffres) #Le nombre de chiffres en binaire
  for i in range(log2):
    somme += chiffres[i]*1<<(log2-i-1) # 1<<(log2-i-1)=2**(log2-i-1) 
  return somme

C=[1,1,1,0,1,1] # 59
N=somme0(C)
print(C,"->",N)

def somme1(chiffres):
  somme = 0
  p2=1
  for i in range(len(chiffres)-1,-1,-1):# en descendant 
    somme += chiffres[i]*p2
    p2 *= 2 # Les puissances de 2 croissantes
  return somme

print(C,"->",somme1(C))

def sommeRecursive(chiffres): 
  if (len(chiffres)==0): return 0
  else: return chiffres[-1]+2*sommeRecursive(chiffres[:-1]) # On recommence en enlevant le bit de poids faible, c'est-à-dire le plus à droite, le dernier dans la liste.

print(C,"->",sommeRecursive(C))

def sommeHorner(chiffres):
  somme = 0
  for i in range(len(chiffres)):
    somme=2*somme+chiffres[i] # Algorithme de Hörner
  return somme

print(C,"->",sommeHorner(C))
########################
def decomp(nombre): # Du poids faible vers le poids fort. Récursif
  if nombre<2: return [nombre]
  else: return decomp(nombre//2)+[nombre % 2]

print(N,"->",decomp(N))

def decompDec(nombre):#Version bits de poids forts -> faibles avec une boucle
  p2=128
  #while (p2<nombre): p2=2*p2
  #p2 vaut maintenant la puissance de 2 la plus petite strictemente supérieure à nombre
  chiffres=[]
  #p2=p2//2 # p2 est la plus grande puissance de 2 <= nombre
  while p2>0:
    if p2<=nombre: 
      chiffres = chiffres+[1] #J'ai besoin de cette puissance de 2 dans ma décomposition
      nombre = nombre - p2
    else: # Je n'ai pas besoin de cette puissance de 2
      chiffres = chiffres+[0]
    p2=p2//2
  return chiffres

  
def decompDecRec(nombre,p2): #Version bits de poids forts -> faibles récursive. p2 est une puissance de 2 supérieure à nombre.
  p2=p2//2
  if(p2<2): return [nombre] # Soit '0', soit '1'
  if(p2<=nombre):
    return [1]+decompDecRec(nombre-p2,p2)
  else:
    return [0]+decompDecRec(nombre,p2)

def decompDecRec2(n,k): #k est ici le degré
    if k == -1:
        return []
    else:
        if n>=1<<k: # 1<<k=2**k
            return[1]+decompDecRec2(n-(1<<k), k-1)
        else:
            return [0]+decompDecRec2(n, k-1)

print("decompDec:"+str(decompDec(N)))
print("decompDecRec2:"+str(decompDecRec2(N,5)))

print(decomp(N))