Comportamento indefinito degli operatori nell'algoritmo di scambio XOR?

Question

void swap(int* a, int* b) { 
    if (a != b) 
     *a ^= *b ^= *a ^= *b; 
} 

Come sopra *a ^= *b ^= *a ^= *b è solo una scorciatoia per *a = *a^(*b = *b^(*a = *a^*b)), potrebbe (ad esempio) il 2 ° *a essere valutati (per la XOR) poco prima del 3 ° *a viene modificato (dai =)?

Non importa se lo scrivo in C99/C11/C++ 98/C++ 11?

Answer 1

Lo standard C++ 11 dice:

5,17/1: l'operatore di assegnazione (=) e il composto operatori di assegnazione tutti gruppo destra a sinistra. (...) l'assegnazione è in sequenza dopo il calcolo del valore degli operandi di destra e di sinistra, e prima del calcolo del valore dell'espressione di assegnazione.

1,9/15: Se un effetto collaterale su un oggetto scalare è non in sequenza rispetto a uno altro effetto collaterale sullo stesso oggetto scalare o un calcolo valore utilizzando il valore dello stesso oggetto scalare il comportamento è indefinito .

Così *a ^= *b viene sequenziato come segue:

1. *a e *b sono calcolati. È NON determinare in quale ordine eseguita
2. l'operazione XOR
3. l'assegnazione avviene, cioè il nuovo valore viene memorizzato in *a
4. il nuovo valore viene utilizzato come risultato dell'espressione (*a ^= *b)

Ora *b ^= *a ^= *b, che secondo la regola di priorità è *b ^= (*a ^= *b):

1. *b e (*a ^= *b) sono calcolati. È NON determinato in quale ordine. Ma come *b non è modificato da (*a ^= *b) non importa.
2. l'operazione XOR viene eseguita
3. l'assegnazione avviene, cioè il nuovo valore viene memorizzato in *b

Ma ora al sequenza specificata con *a ^= *b ^= *a ^= *b che è secondo regole di priorità *a ^= (*b ^= (*a ^= *b)):

1. *a e (*b ^= (*a ^= *b)) sono calcolati. È NON determinato in quale ordine. Ma come *a IS modificato da (*b ^= (*a ^= *b)). Quindi il risultato dipenderà da quale valore viene calcolato per primo. Questo è chiaramente un U.B.

Supponiamo *a viene valutata prima, (vale a dire prima di tutto):
si dovrebbe ottenere il valore originale di esso, che verrà XOR con il valore di (*b ^= (*a ^= *b)), che è l'originale *b XORed con originali *a xored di nuovo con *b. Ciò comporterà 0 (che verrà memorizzato in *a).

Supponiamo (*b ^= (*a ^= *b)) viene valutata per prima, allora il risultato è l'originale *a, ma il contenuto di *a viene modificato all'originale *a XOR con l'originale *b. Così questo comporterà l'originale *b (che saranno memorizzati in *a)

proposito, in entrambi i casi, *b contiene il valore originale di *a XORed due volte con *b senso che *b conterrà l'originale *a.

Conclusioni Qui è dimostrato che il valore finale del *b è univocamente determinata da questa espressione, ma che il valore finale del *a non è univocamente definita (due valori possibili). Quindi è chiaramente un NON RISULTATO/RISULTATO NON DEFINITO! Può scambiare o perdere *a a seconda del compilatore.

Come fare lo scambio di sicuro?

Ho dimostrato sopra che i primi due compiti composti sono ben specificati. Quindi dobbiamo solo assicurarci che l'ultimo compito composto sia fatto dopo di esso. Ciò può essere garantito da un operatore virgola:

5,18/1: Una coppia di espressioni separate da una virgola viene valutata da sinistra a destra e il valore dell'espressione sinistra viene scartato

Quindi, il seguente avrebbe funzionato:

void safe_swap(int* a, int* b) { 
    if (a != b) 
     *b ^= *a ^= *b, *a ^= *b; 
}