Dlaczego a = (A+b) - (b = a) jest złym wyborem dla zamiany dwóch liczb całkowitych?

Moje pytanie brzmi - czy jest to dopuszczalne rozwiązanie do zamiany dwóch liczb całkowitych?

Dlaczego a = (A+b)-(b=a) jest złym wyborem dla zamiany dwóch liczb całkowitych?

Z następujących powodów:

1) jak zauważyłeś, nie ma gwarancji w C, że faktycznie to robi. Może zrobić wszystko.

2) Załóżmy dla dobra argument, że naprawdę zamienia dwie liczby całkowite, tak jak w C#. (C# gwarantuje, że skutki uboczne zdarzają się od lewej do prawej.) Kod nadal byłby nie do przyjęcia, bo zupełnie nie jest oczywiste, jakie jest jego znaczenie! Kod nie powinien być zbiorem sprytnych sztuczek. Napisz kod dla osoby, która przyjdzie po ciebie, która musi go przeczytać i zrozumieć.

3) ponownie, Załóżmy, że to działa. Kod jest nadal nie do zaakceptowania, ponieważ jest to po prostu fałsz:

Natknąłem się na ten kod dla Zamiana dwóch liczb całkowitych bez użycia zmiennej tymczasowej lub użycia operatorów bitowych.

4) to działa tylko dla liczb całkowitych. Wiele rzeczy wymaga wymiany innych niż liczby całkowite.

Krótko mówiąc, poświęć swój czas koncentrując się na pisaniu kodu, który jest oczywiście poprawny, zamiast próbować wymyślać sprytne sztuczki, które naprawdę pogarszają sprawę.

Istnieją co najmniej dwa problemy z a=(a+b)-(b=a).

Jeden, o którym wspominasz: brak punktów sekwencji oznacza, że zachowanie jest niezdefiniowane. Jako takie, wszystko w ogóle może się zdarzyć. Na przykład, nie ma gwarancji, która jest oceniana jako pierwsza: a+b lub b=a. Kompilator może najpierw wygenerować kod do przypisania lub zrobić coś zupełnie innego.

Innym problemem jest fakt, że przepełnienie arytmetyki podpisanej jest niezdefiniowanym zachowaniem. If a+b overflows nie ma gwarancji wyników; nawet wyjątek może zostać wyrzucony.

Oprócz innych odpowiedzi na temat niezdefiniowanego zachowania i stylu, jeśli piszesz prosty kod, który używa tylko tymczasowej zmiennej, kompilator może prawdopodobnie śledzić wartości i nie zamieniać ich w wygenerowanym kodzie, a w niektórych przypadkach po prostu używać zamienionych wartości później. Nie można tego zrobić z Twoim kodem. Kompilator jest zwykle lepszy od Ciebie w mikro optymalizacjach.

Więc prawdopodobnie Twój kod jest wolniejszy, trudniejszy do zrozumienia i prawdopodobnie nierzetelny, niezdefiniowany też.

Jeśli używasz gcc i -Wall kompilator już cię ostrzega

A. C: 3: 26: warning: operation on ' b ' may be undefined [- Wsequence-point]

void swap1(int *a, int *b)
{
    *a = (*a + *b) - (*b = *a);
}

void swap2(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

I sprawdzić kod zespołu

swap1:
.LFB0:
    .cfi_startproc
    movl    (%rdi), %edx
    movl    (%rsi), %eax
    movl    %edx, (%rsi)
    movl    %eax, (%rdi)
    ret
    .cfi_endproc

swap2:
.LFB1:
    .cfi_startproc
    movl    (%rdi), %eax
    movl    (%rsi), %edx
    movl    %edx, (%rdi)
    movl    %eax, (%rsi)
    ret
    .cfi_endproc

Nie widać korzyści z zaciemniania kodu.

Patrząc na kod C++ (g++), który robi w zasadzie to samo, ale bierze pod uwagę move

#include <algorithm>

void swap3(int *a, int *b)
{
    std::swap(*a, *b);
}

Daje identyczne wyjście montażu

_Z5swap3PiS_:
.LFB417:
    .cfi_startproc
    movl    (%rdi), %eax
    movl    (%rsi), %edx
    movl    %edx, (%rdi)
    movl    %eax, (%rsi)
    ret
    .cfi_endproc

Wypowiedź:

a=(a+b)-(b=a);

Wywołuje nieokreślone zachowanie. Drugi w cytowanym ustępie jest naruszony:

(C99, 6.5p2) " pomiędzy poprzednim i następnym punktem sekwencji obiekt powinien mieć zapisaną wartość zmodyfikowaną co najwyżej raz przez ocenę wyrażenia. ponadto poprzednia wartość jest odczytywana tylko w celu określenia wartości, która ma być przechowywana."

A question was posted back in 2010 z dokładnie tym samym przykładem.

a = (a+b) - (b=a);

Steve Jessop ostrzega przed nim:

Zachowanie tego kodu jest nieokreślone. ZARÓWNO a jak i b są czytane i napisany bez interweniującego punktu sekwencji. Na początek, kompilator miałby prawo do oceny b = A przed ocena a + b.

Oto Wyjaśnienie z pytania zamieszczonego w 2012. Zauważ, że próbka nie jest dokładnie to samo z powodu braku nawiasów, ale odpowiedź jest nadal aktualna.

W C++ podwyrażenia w wyrażeniach arytmetycznych nie mają czasu zamawiam.

a = x + y;

Czy X jest oceniane jako pierwsze, czy y? Kompilator może wybrać albo, albo może wybierz coś zupełnie innego. Kolejność oceny nie jest to samo co pierwszeństwo operatora: pierwszeństwo operatora jest ściśle określone, oraz kolejność oceny jest zdefiniowana tylko dla ziarnistości że twój program ma punkty sekwencji.

W rzeczywistości na niektórych architekturach możliwe jest emitowanie kodu, który ocenia zarówno x, jak i y w tym samym czasie-na przykład VLIW architektury.

Teraz dla standardowych cytatów C11 z N1570:

Załącznik J. 1 / 1

Jest to nieokreślone zachowanie, gdy:

- kolejność w jakich podwyrażeniach są oceniane i w jakiej kolejności efekty zachodzą, z wyjątkiem funkcji-wywołania (), &&, ||, ? :, oraz operatory przecinkowe (6.5).

- kolejność, w jakiej oceniane są operandy operatora przyporządkowania (6.5.16).

Załącznik J. 2 / 1

Jest niezdefiniowanym zachowaniem, gdy:

- efekt uboczny na obiekcie skalarnym jest niespójny względem inny efekt uboczny na tym samym obiekcie skalarnym lub obliczenie wartości używanie wartości tego samego skalara obiekt (6.5).

6.5/1

Wyrażenie jest sekwencją operatorów i operandów, które określają obliczanie wartości lub wyznaczanie obiektu lub funkcji, lub powoduje to skutki uboczne lub wykonuje ich kombinację. Obliczenia wartości operandów operatora są sekwencjonowane przed obliczeniem wartości wyniku operatora.

6.5/2

Jeśli efekt uboczny na obiekcie skalarnym jest nierozliczone w stosunku do albo inny efekt uboczny na tym samym obiekcie skalarnym lub wartości obliczenie przy użyciu wartości tego samego skalarnego obiektu, zachowanie jest undefined. Jeśli istnieje wiele dozwolonych zamówień z podwyrażenia wyrażenia, zachowanie jest niezdefiniowane, jeśli takie niezrównoważony efekt uboczny występuje w każdym z zamówień.84)

6.5/3

Grupowanie operatorów i operandów jest wskazane przez składnię.85) Z wyjątkiem określone później, skutki uboczne i obliczenia wartości subekspresje nie są wyrównane.86)

Nie powinieneś polegać na nieokreślonym zachowaniu.

Niektóre alternatywy: w C++ możesz użyć

  std::swap(a, b);

XOR-swap:

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

Problem polega na tym, że zgodnie ze standardem C++

Z wyjątkiem przypadków, gdy zaznaczono, oceny operandów poszczególnych operatorów i podekspresji poszczególnych wyrażeń są niezrównoważone.

Więc to wyrażenie

a=(a+b)-(b=a);

Ma nieokreślone zachowanie.

Możesz użyć XOR swap algorithm Aby zapobiec problemom z przepełnieniem i nadal mieć jedną linijkę.

Ale skoro masz c++ znacznik, wolałbym prosty std::swap(a, b), aby był łatwiejszy do odczytania.

Oprócz problemów wywoływanych przez innych użytkowników, ten typ wymiany ma inny problem: domena .

A jeśli a+b przekroczy granicę? Załóżmy, że pracujemy z numerami od 0 do 100. 80+ 60 wyszłoby poza zasięg.