Re: Problème de l'arrêt

Le 01/10/2022 à 12:50, Michel Talon a écrit :

>

Mais oui, pour des nombres positifs ce que tu dis est forcément vrai, du
fait que s'il y a plusieurs boucles c'est à cause de la propagation d'une
retenue, à chaque fois au rang suivant.

 
En fait, tel que je le vois, m+n est un invariant de la boucle. Pourquoi?
 
m devient le XOR de m et n, c'est à dire a les bits qui sont soit dans m
soit dans n mais pas les deux.
 
n devient le double (à cause du << 1) du AND de m et n c'est à dire les
bits qui sont à la fois dans  m et n.  Evidemment quand on fait m+n
le AND apparaît 2 fois, et le XOR une fois, donc il est "clair" que m+n
a la même valeur que m ^ n + (m & n) << 1.

Oui, je suis d'accord avec tout ce qui précède.

Comme XOR(m,n) <= max(m,n) et idem pour AND(m,n) et que le AND est
poussé à gauche à chaque étape par le << 1 il va venir un moment où
n est trop grand pour avoir des bits en commun avec m, donc à l'étape
suivante on a n=0 et donc le while se termine et la fonction retourne
n+m puisque le dernier n vaut 0.

Oui, encore une fois si les deux nombres sont positifs.

Il se trouve que si les deux nombres sont négatifs, ou si l'un des
deux est négatif et que sa valeur absolue est strictement supérieure
à l'autre nombre, le while se terminera aussi.

En revanche, si la valeur absolue du nombre négatif est inférieure ou
égale au nombre positif, alors il reste vrai que m+n est un invariant
de la boucle (invariant qui est donc positif ou nul), mais cette
boucle ne se terminera jamais : m et n seront de plus en plus grands
en valeur absolue, avec m négatif et n positif.

--
Olivier Miakinen