Permutation de deux variable

[invite414aeef9]

Bonjour,
Ma question est :
Est-ce qu' on peut permuter la valeur de deux variables sans utiliser une troisieme.
-----

[invite2d7144a7]

Bonjour,

Oui, avec une série de XOR :
(En C, l'opérateur ^= est XOR)

        a^=b;
        b^=a;
        a^=b;

[Jack]

A la condition qu'elles soient entières ou d'un type dérivé.

[invite2d7144a7]

Bonjour,

A la condition qu'elles soient entières ou d'un type dérivé.

Non, il suffit d'adapter, la seule condition impérative est qu'elles aient la même taille.

MAIS il y quand même une condition nécessaire : elles doivent être différentes, il faut tester avant.

On peut par exemple appliquer à 2 chaînes de même longueur, en swappant caractère par caractère.

[A voir en vidéo sur Futura]

[pm42]

A la condition qu'elles soient entières ou d'un type dérivé.

Dans les langages qui permettent la manipulation directe de la mémoire au niveau de l'octet, genre C via la cast d'une adresse en char*, on doit pouvoir généraliser le Xor ci-dessus à n'importe quel type peut-être ?

[Jack]

Non, il suffit d'adapter, la seule condition impérative est qu'elles aient la même taille.

En effet, on peut puisque qu'on échange les octets de même rang, peu importe le codage de l'ensemble.

[jiherve]

bonsoir
je ne suis pas sur que cela reponde à la question!
amha ce qu'il cherche c'est a <=> b
donc la suite :

c:= a;
a:= b;
b:= c;
implicitement ou explicitement il faut une variable tampon
a^= b; => a xor b
b^= a; => b xor ( a xor b) = b
a^= b; => a xor b ????
les instructions sont séquentielles du moins c’était le cas de mon temps
JR

[pm42]

implicitement ou explicitement il faut une variable tampon

Non justement.

a^= b; => a xor b
b^= a; => b xor ( a xor b) = b
a^= b; => a xor b ????
les instructions sont séquentielles du moins c’était le cas de mon temps

Tu as essayé ? Parce que ça marche. Notamment parce que b xor (a xor b) = a et non pas = b comme tu l'as écrit.

[jiherve]

Re
oui erreur, il m'arrive de raisonner de travers.
désolé
JR

[pm42]

Re
oui erreur, il m'arrive de raisonner de travers.
désolé

Rien de grave, ça arrive à tout le monde (et à moi souvent).

[polo974]

Bonjour,
...
MAIS il y quand même une condition nécessaire : elles doivent être différentes, il faut tester avant.
...

Ah bon, et pourquoi donc ne pourrait-on pas les xorer si elles ont la même valeur ? ? ?

(au fait, c'est un sujet d'exo ou bien je me trompe ?)

[CM63]

En fait quand on fait:

a^=b

On passe implicitement par une "case" intermédiaire, qui est certes dans le registre du processeur, et non pas en mémoire, mais bon, la nuance est subtile.
Sans compter que cette "économie de variable" coûte cher: puisqu'il faut exécuter 3 instructions.

[pm42]

Tu ne sais pas si le compilateur n'a pas mis ces variables dans des registres ce qu'il fait des que possible. Ni le coût d'un accès mémoire comparé à un xor.
Mais effectivement une variable intermédiaire utilisée localement doit permettre une meilleure optimisation.

[invite2800a7c8]

Bonjour,
Ma question est :
Est-ce qu' on peut permuter la valeur de deux variables sans utiliser une troisieme.

Salut,
ben oui avec une pile lifo par exemple.
mais ce sera un peu tricher puisque l'on va se servir des registres internes du processeur.
En haut niveau on aura l'impression de n'utiliser que deux variables, mais au niveau du processeur ce ne sera pas le cas.

Une petite routine en langage machine x.86

0 [EBP] EAX MOV                
EBX 0 [EBP] MOV                
EAX EBX MOV                   
RET

Cordialement
Ludwig

[Jack]

Sans compter que cette "économie de variable" coûte cher: puisqu'il faut exécuter 3 instructions.

C'est pas faux:

	int x = 5, y = 3;
0032139E  mov         dword ptr [x],5  
003213A5  mov         dword ptr [y],3  
        x ^= y;
00DD13AC  mov         eax,dword ptr [x]  
00DD13AF  xor         eax,dword ptr [y]  
00DD13B2  mov         dword ptr [x],eax  
	y ^= x;
00DD13B5  mov         eax,dword ptr [y]  
00DD13B8  xor         eax,dword ptr [x]  
00DD13BB  mov         dword ptr [y],eax  
	x ^= y;
00DD13BE  mov         eax,dword ptr [x]  
00DD13C1  xor         eax,dword ptr [y]  
00DD13C4  mov         dword ptr [x],eax

[invite9dc7b526]

sinon, pour des variables numériques, il y a l'astuce (qui a des variantes)

a = b - a
b = b - a
a = a + b

[invite9dc7b526]

on peut aussi écrire par exemple

a = ab
b = a/b
a = a/b

en fait on a besoin d'une fonction de 2 variables f telle qu'il existe des fonctions g et h et que si f(x,y)=z alors x=g(y,z) et y=h(x,z). Et il suffit de prendre une fonction symétrique en x,y telle que sa dérivée par rapport à x existe et soit non nulle (comme f(x,y)=x+y ou f(x,y)=xy).

[invite2d7144a7]

Bonjour,

Oui, mais ATTENTION : si les variables en question sont des réels (float ou double), il y aura des approximations lors des calculs, et tu ne retrouveras pas les bonnes valeurs, sauf par chance.

[polo974]

on peut aussi écrire par exemple

a = ab
b = a/b
a = a/b
....

non, car ab risque fort de déborder...

sinon, on peut aussi passer par une série de shift en passant par la retenue (mémoire 1 bit)...

[danyvio]

sinon, pour des variables numériques, il y a l'astuce (qui a des variantes)

a = b - a
b = b - a
a = a + b

C'est ce que j'ai utilisé de temps en temps. La seule contrainte est que la somme des valeurs absolues des variables initiales ne provoque pas d'overflow.

[CM63]

Bonjour,

Lorsque, dans certains langages comme Python ou Ruby, on fait:

a,b = b,a

Évidement, c'est de la triche, car une fois interprétée cette instruction passe bien par une variable temporaire.