Discussion :

[NVCfrm]

Bonsoir,

En pratique (en C donc) ça ne le fait pas aussi bien que la version avec XOR : si tu échanges des entiers signés et que tu fais un overflow, paf ! Comportement indéterminé.
En XOR, pas d’overflow possible.

Quelque chose qui m'échappe.
Comment le comportement est-il différent avec un signed ou unsigned?
Quelle version XOR?

Comment transcrire arithmétiquement la logique: ((a + b) - b) == ((a - b) + b)?

J'ai beau imaginé les différents cas qui me viennent à l'esprit sur l'exploitation des 2 expressions, je n'arrive pas à trouver le cas où j'aurais droit à un paf, sans que ça ne soit le cas pour l'autre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
        #define invert_1(x,y) x ^= y, y ^= x, x ^= y
 
        #define invert_2(a,b) (b = (a-b), a = (a-b), b = (b+a))

[Sve@r]

Bonsoir,

Quelque chose qui m'échappe.
Comment le comportement est-il différent avec un signed ou unsigned?

Il n'a pas dit que le comportement était différent avec un signed d'un unsigned. il a juste donné l'exemple d'un signed pour dire que l'addition de deux nombres dont le résultat dépasse la capacité max d'un signed donnait un comportement indéterminé (pour moi ça coupait plutôt les bits qui dépassent ce qui est parfaitement déterminé mais je ne suis pas sûr de moi donc j'ai pas répondu)...

Quelle version XOR?

Il n'a pas parlé d'une version XOR particulière mais de la version du code utilisant XOR...

J'ai beau imaginé les différents cas qui me viennent à l'esprit sur l'exploitation des 2 expressions, je n'arrive pas à trouver le cas où j'aurais droit à un paf, sans que ça ne soit le cas pour l'autre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
        #define invert_1(x,y) x ^= y, y ^= x, x ^= y
 
        #define invert_2(a,b) (b = (a-b), a = (a-b), b = (b+a))

Moi non plus car comme la perte de "ce qui dépasse" donne des calculs cycliques (par exemple sur un signed char alors 127 + 1 = -128 et -128 - 1 = 127) on retombe toujours sur nos pattes.

En plus, je serais curieux de voir si le codage très spécifique d'un float (avec mantisse et exposant) permet d'utiliser le XOR pour les permuter...

[grim7reaper]

Bonsoir,

Quelque chose qui m'échappe.
Comment le comportement est-il différent avec un signed ou unsigned?

L’overflow sur les entiers non signés est défini (quasi-sûr, mais à vérifier). Celui sur les entiers signés ne l’est pas (ça j’en suis sûr).

La version XOR fait des manipulations bits à bits, pas de problème.
La version arithmétique fait des additions (risque d’overflow) et des soustractions, problème.

Quelle version XOR?

À propos du swap de deux variables.

Soit le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <limits.h>
 
void xor_swap(int* x, int* y);
void add_swap(int* x, int* y);
 
int main(void)
{
    int a = INT_MAX;
    int b = 1;
    printf("bef: %d %d\n", a, b);
    xor_swap(&a, &b);
    printf("aft: %d %d\n", a, b);
    return 0;
}
 
void xor_swap(int* x, int* y)
{
    if (x != y)
    {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
}
 
void add_swap(int* x, int* y)
{
    if (x != y)
    {
        *x = *x + *y;
        *y = *x - *y;
        *x = *x - *y;
    }
}

En utilisant une option fort sympathique de clang, c’est très facilement visible.
Avec le xor_swap :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
% clang -fsanitize=undefined -o swap swap.c
% ./swap
bef: 2147483647 1
aft: 1 2147483647

Et si on remplace le xor_swap par un add_swap :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
% clang -fsanitize=undefined -o swap swap.c
% ./swap
bef: 2147483647 1
swap.c:32:17: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'
swap.c:33:17: runtime error: signed integer overflow: -2147483648 - 1 cannot be represented in type 'int'
swap.c:34:17: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int'
aft: 1 2147483647

Il n'a pas dit que le comportement était différent avec un signed d'un unsigned. il a juste donné l'exemple d'un signed pour dire que l'addition de deux nombres dont le résultat dépasse la capacité max d'un signed donnait un comportement indéterminé (pour moi ça coupait plutôt les bits qui dépassent ce qui est parfaitement déterminé mais je ne suis pas sûr de moi donc j'ai pas répondu)...

C’est ce que la plupart des compilateurs font (sauf en mode optimisations, on peut avoir des surprises). Mais la norme dit bien que c’est comportement indéterminé.

Moi non plus car comme la perte de "ce qui dépasse" donne des calculs cycliques (par exemple sur un signed char alors 127 + 1 = -128 et -128 - 1 = 127) on retombe toujours sur nos pattes.

La norme n’impose pas l’usage du complément à 2. Même si en pratique, on trouve rarement autre chose de nos jours.

En plus, je serais curieux de voir si le codage très spécifique d'un float (avec mantisse et exposant) permet d'utiliser le XOR pour les permuter...

L’opérateur ^ ne s’applique pas sur les nombres flottants donc c’est vite vu.
Cela dit, en castant comme un bourrin en type entier suffisament large ça passera et tes deux nombres flottants seront bien échangé.
Ça bosse bit à bit, donc ça fonctionne aussi bien pour un int que pour un float ou ce que tu veux. Comme memcpy qui copie (de façon bête et méchante) tout ce que tu veux.

[NVCfrm]

Bonsoir grim7reaper

Je ne connais pas cette option. Est ce que tu as essayé un underflow pour les 2 cas?
Si je comprends bien, cela s'expliquerait par les différences des 2 opérations?
Si je suis toujours ,l'addition nécessite un registre supplémentaire à la différence du xor. Comme l'a déjà fait remarquer un intervenant le xor a l'avantage d'épargner un registre.
L'explication ne se trouve-t-elle pas là? Pas de résultat à lire pour scruter le bit d'overflow?
Cela ne fait-il pas que le xor natif peut être une faille potentielle d'écriture en mémoire non?
Je m'y perds un petit peu.
Merci de vos lumières.
Par contre:

L’overflow
...
Ça bosse bit à bit, donc ça fonctionne aussi bien pour un int que pour un float ou ce que tu veux. ...

pour une addition ou soustraction ?
Sinon l'avantage du xor est incontestable dans bien de cas n'est pas en cause. Les opérations arithmétiques étant construites par une surcharge de xor.

[grim7reaper]

Est ce que tu as essayé un underflow pour les 2 cas?

Non, j’ai juste essayé un overflow dans les deux cas.
Le fait est que c’est défini pour les unsigned :

A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

mais pas pour les signed.

An example of undefined behavior is the behavior on integer overflow.

Je pense que ça vient du fait que en unsigned y’a pas 42 façons de gérer le trucs. Alors qu’en signed, ça va dépendre de comment tu les représentes.
Et comme le C n’impose pas de représentation :

If the sign bit is one, the value shall be modified in one of the following ways:
— the corresponding value with sign bit 0 is negated (sign and magnitude);
— the sign bit has the value −(2 N ) (two’s complement);
— the sign bit has the value −(2 N − 1) (ones’ complement ).
Which of these applies is implementation-defined, as is whether the value with sign bit 1 and all value bits zero (for the first two), or with sign bit and all value bits 1 (for ones’ complement), is a trap representation or a normal value.

Je pense que la différence vient de là.

Si je comprends bien, cela s'expliquerait par les différences des 2 opérations?

Oui.
Le XOR est une opération logique.
L’addition et la soustraction sont des opérations arithmétiques.

Si je suis toujours ,l'addition nécessite un registre supplémentaire à la différence du xor. Comme l'a déjà fait remarquer un intervenant le xor a l'avantage d'épargner un registre.
L'explication ne se trouve-t-elle pas là? Pas de résultat à lire pour scruter le bit d'overflow?

Pas vraiment de rapport avec le nombre de registres utilisés.
C’est seulement que le concept d’overflow n’a aucun sens pour une opération logique.
Le XOR il bosse bit à bit et il se base sur une table de vérité.
Il prend un nombre A à N bits, un nombre B à N bit et il va produire un nombre C à N bits.

Par contre une opération arithmétique peut faire un overflow car le résultat peut nécessiter un nombre de bits plus grand que celui des opérandes.

Cela ne fait-il pas que le xor natif peut être une faille potentielle d'écriture en mémoire non?

C’est-à-dire ?

Par contre:

Ça bosse bit à bit, donc ça fonctionne aussi bien pour un int que pour un float ou ce que tu veux. ...

pour une addition ou soustraction ?

Ni l’une ni l’autre. Je parlais seulement du swap.

[NVCfrm]

bonjour,
merci pour ces explications fort utiles.
Je suis encore toujours sur ma soif de détails plus ou moins obscurs, ou du besoin de discernement assez clair des nuances sur l'organisation des différences des opérations.

Je commences à comprendre mieux certaines de tes remarques.

Bosser bit à bit de façon logique implique 2 entrées et une sortie dirigée vers l'une des entrées.
Supposons 'a' une entrée comportant une plage de 4 bits en entrée et 'b' faisant 3 bits qui est la deuxième entrée.
Pour tout bit de 'a' ou 'b' aux positions correspondantes un xor pour basculer les bits de l'un sur l'autre. Est ce exact?

Par exemple:

      | 1 | 0 | 1 | 0 |
   xor  
          | 1 | 0 | 1 |
     ___________________
    = | 1 | 1 | 1 | 1 |

Cette opération en fonction du sens d'écriture du résultat s'écrira dans 'a' ou 'b'.
15 et 7 en décimale pour l'un et l'autre.
Donc le résultat est logiquement promu en 4 bits.
Dans le cas de 2 objets de 4 bits faisant 15 et 1 en nombre décimaux, ou passera le bit supplémentaire du résultat?
Comment se déroulera la logique avec le bit manquant ou en excès selon les cas?
Et en arithmétique?

[Sve@r]

Bosser bit à bit de façon logique implique 2 entrées et une sortie dirigée vers l'une des entrées.
Supposons 'a' une entrée comportant une plage de 4 bits en entrée et 'b' faisant 3 bits qui est la deuxième entrée.
Pour tout bit de 'a' ou 'b' aux positions correspondantes un xor pour basculer les bits de l'un sur l'autre. Est ce exact?

Par exemple:
| 1 | 0 | 1 | 0 |
xor
| 1 | 0 | 1 |
___________________
=| 1 | 1 | 1 | 1 |

C'est exact (mais l'affichage le rend mal).

• 1 xor 1 = 0
• 0 xor 0 = 0
• 1 xor 0 = 0 xor 1 = 1

En fait, le xor est une conjugaison de "et", de "non" et de "ou"
a xor b = (a et non(b)) ou (non(a) et b)

Cette opération en fonction du sens d'écriture du résultat s'écrira dans 'a' ou 'b'.
15 et 7 en décimale pour l'un et l'autre.
Donc le résultat est logiquement promu en 4 bits.

Il est promu dans l'opérande le plus large utilisé (donc ici 4 bits).

Dans le cas de 2 objets de 4 bits faisant 15 et 1 en nombre décimaux, ou passera le bit supplémentaire du résultat?

Pourquoi "bit supplémentaire" ??? Même si parfois un xor ressemble à une addition ce n'en est pas une. 15 (1111) xor 1 (0001) donnera 1110 soit 14 (toujours sur 4 bits)

Et en arithmétique?

Je vais parler de "and" et de "or" pour essayer de clarifier mon texte (quand je dirai "et" ce sera alors la conjonction de coordination et non l'opérateur booléen).

Donc on associe généralement "and" à la multiplication. Et "or" à l'addition. Parce que si on remplace "and" et "or" par une multiplication ou une addition, le résultat reste identique à celui des tables de Boole (1 * 0 = (1 and 0) = 0; 1*1 = (1 and 1) = 1; 0+0 = (0 or 0) = 0 et 0+1 = (0 or 1) = 1).
Pour le "non" c'est un peu plus subtil. non(0) = 1 et non(1)=0. On peut alors le traduire par non(x)=1-x => (1-1 = 0 et 1-0=1).

Si on applique alors ces équivalences au xor (qui est, rappelons-le, un compactage de "et", de "ou" et de "non", alors cela donnerait
a xor b = (a and non(b)) or (non(a) and b)
Traduisons cela en algèbre classique

• 0 xor 0 = (0 * (1-0)) + ((1-0) * 0) = 0
• 0 xor 1 = (0 * (1-1)) + ((1-0) * 1) = 1
• 1 xor 0 = (1 * (1-0)) + ((1-1) * 0) = 1
• 1 xor 1 = (1 * (1-1)) + ((1*1) * 1) = 0

Donc le résultat algébrique correspond au résultat booléen... mais à condition qu'on reste en binaire. Parce que 15 xor 14 reste intraduisible algébriquement en calcul décimal...

[Obsidian]

C'est exact (mais l'affichage le rend mal).

Corrigé avec les balises PRE.

[diogene]

Cette histoire de promotion sur 4 bits ou sur le type de l'opérande de type "le plus grand" ne reflète pas la conception du C. Par exemple, même si a et b sont tous deux des (unsigned) char, le résultat de a^b ne sera pas un (unsigned) char à cause de la promotion des 'petits' entiers.

[NVCfrm]

Bonsoir Sve@r,

Donc le résultat algébrique correspond au résultat booléen... mais à condition qu'on reste en binaire. Parce que 15 xor 14 reste intraduisible algébriquement en calcul décimal...

Cette dernière remarque a été pour moi un éclair!
L'exemple 15 xor 14 est le cas qu'il me fallait pour mieux cerner la logique xor. C'est l'illustration des propos de grim7reaper.

Bonsoir diogene
C'est un honneur de lire tes remarques sur les petites lacunes intrigantes de ces derniers échanges.
Merci à tous.