Écrire compare(s, t) qui, données deux écritures binaires sans zéros…

L'idée. Sans zéros inutiles à gauche, la longueur décide en premier : plus de bits signifie plus grand. À longueur égale, on compare les bits de gauche à droite ; le premier écart tranche, car un bit de poids $2^i$ pèse plus que tous les bits suivants réunis ($2^i>2^{i-1}+\cdots +2^0=2^i-1$).

def compare(s, t):
    """-1, 0 ou 1 selon que s est <, = ou > à t.

    Précondition : s et t sont des écritures binaires sans
    zéros inutiles à gauche (sauf la chaîne "0").
    """
    if len(s) != len(t):
        return -1 if len(s) < len(t) else 1
    for i in range(len(s)):
        if s[i] != t[i]:
            return -1 if s[i] == "0" else 1
    return 0

Validation.

for x in range(0, 200):
    for y in range(0, 200):
        attendu = (x > y) - (x < y)
        assert compare(vers_base(x, 2), vers_base(y, 2)) == attendu

$40000$ cas passent.

Piège : oublier la précondition. Avec "0011" et "11", la fonction répondrait « le premier est plus grand » alors qu'ils sont égaux : c'est la comparaison des longueurs qui devient fausse dès qu'on autorise les zéros de tête.