Vertauschen von drei Variablen

[C-Progammer (Gast)]

Hallo zusammen,
ich hab eine Aufgabe fürs Studium, die mich einfach verrückt werden 
lässt. Hoffentlich kann einer von euch die Aufgabe lösen:

Zunächst soll ich den drei Variablen x, y und z einen beliebigen Wert 
zuordnen. Dannach sollen die Werte vertauscht werden:
Der Wert von x soll zur Variable y
Der Wert von y soll zur Variable z
Der Wert von z soll zur Variable x

Einschränkungen:
1. Keine weitere Hilfsvariable
2. maximal 4 Zuweisungen
Alles in der Programmiersprache C.

Ich hoffen ihr könnt mir weiterhelfen.

[Hmm (Gast)]

Wenn solche Aufgaben gestellt werden, dann wurden einem in der Regel 
auch die Voraussetzungen dafür gegeben.
Habt ihr die Bitweisen Operationen schon gelernt? Falls ja, dann weisst 
Du den Weg.
Kleiner Tip: Überleg Dir zunächst wie man zwei Variablen ohne 
Hilfsvariable tauscht.

[C-Progammer (Gast)]

Ja hatten wir.
Für 2 Variablen würde ichs mit ex-or lösen:

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

aber das ist ja nicht so leicht auf drei variablen übertragbar oder?

[Rene H. (Gast)]

Was ist da anders?

Das Prinzip (Dreieckstausch) ist das selbe.

Grüsse,
R.

[Hmm (Gast)]

>Der Wert von x soll zur Variable y
>Der Wert von y soll zur Variable z
>Der Wert von z soll zur Variable x

       x
      / \
     z---y

Nimm an, Du hast schon x mit y vertauscht. Das gibt x' = y und y' = x.

       x'
      / \
     z---y'

bzw. unter der Annahme das nur die Inhalte gewechselt haben, aber nicht 
die Positionen im Diagramm:

       y(x)
      / \
     z---x(y)

Die Forderung "Der Wert von x soll zur Variable y" ist also schon 
erfüllt.

Was musst Du nun noch machen?

Tip: Lass Dich nicht davon verwirren, das bei zwei Variablen zwei 
Exor-Operationen erfolgen. Nimm also nicht an das die Anzahl der 
Variablen identisch mit der Anzahl Operationen sind.

[Hmm (Gast)]

Kleiner Tip noch: Bei solchen völlig "unlösbaren" Aufgaben, probiere 
einfach mal aus, wie weit Du mit dem schon bekannte kommst, schaue Dir 
die Zwischenergebnisse an und lasse Dich von Deiner Phantasie oder auch 
Intuition leiten. Patentrezepte zur Lösung von Aufgaben gibt es leider 
nicht.

Das ist der Fall aus der Schule wo Du Aufgaben bekommst, die eine sog. 
"Übertragungsleistung" erfordern. Also die Anwendung von einem oder 
mehreren bekannten Verfahren auf unbekannte Situationen.

[Hmm (Gast)]

Uups. Addieren der Zahlen von 1 bis 9 muss ich noch üben. :-)

>Tip: Lass Dich nicht davon verwirren, das bei zwei Variablen drei
>Exor-Operationen erfolgen. Nimm also nicht an das die Anzahl der
>Variablen identisch mit der Anzahl Operationen plus Eins sind.

[C-Progammer (Gast)]

danke für die Tipps ;)

Wenn ich nach deinem Dreiecken gehe müsste ich ja (ich gehe davon aus x 
und y sind vertauscht) noch y und z miteinander tauschen. richtig?

y=y^z
z=y^z
y=y^z

[SummerWilli (Gast)]

Geht auch mit Additionen:
x = x+y+z
z = x-y-z
y = x-z-y
x = x-z-y

[C-Anfänger (Gast)]

C-Progammer schrieb:
> Wenn ich nach deinem Dreiecken gehe müsste ich ja (ich gehe davon aus x
> und y sind vertauscht) noch y und z miteinander tauschen. richtig?
>
> y=y^z
> z=y^z
> y=y^z

dann kommst du aber auf mehr als 4 zuweisungen.

[C-Progammer (Gast)]

ja du hast recht, dann werdens mehr als 4. Dann weis ich auch nicht 
weiter. Des mit dem addieren ist eine gute möglichkeit!

[Mac (Gast)]

a = a ^ b ^ c // a==a^b^c
b = a ^ b ^ c // b==(a^b^c)^b^c==a
c = a ^ b ^ c // c==(a^b^c)^a^c==b
a = a ^ b ^ c // a==(a^b^c)^a^b==c

Die Addiermethode ist immer problematisch wg. potentieller 
Integer-Überläufe.

[Zahnfee (Gast)]

SummerWilli schrieb:

> Geht auch mit Additionen:
> x = x+y+z
> z = x-y-z
> y = x-z-y
> x = x-z-y

Geht nicht.

Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z 
ist 32.757 dann kommt es zu einem Überlauf.

[Floh (Gast)]

Typisch akademisches Beispiel ohne Praxisbezug.
Mit exor kommst du auf zuviele Zwischenschritte, mit Addition läufst du 
Gefahr, dass die Variable überlaufen kann.
Eine Zwischenvariable wäre halt zu einfach zu verstehen, könnte jeder 
Trottel und wäre sogar überlaufsicher.

[Peter II (Gast)]

Zahnfee schrieb:
> Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z
> ist 32.757 dann kommt es zu einem Überlauf.

und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit 
egal sein.

[Zahnfee (Gast)]

Peter II schrieb:
> Zahnfee schrieb:
>> Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z
>> ist 32.757 dann kommt es zu einem Überlauf.
>
> und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit
> egal sein.

Sollte? LOL. Beweis.


Peter: "Herr Lehrer, meine Lösung sollte schon richtig sein."

[Mac (Gast)]

Floh schrieb:
> Mit exor kommst du auf zuviele Zwischenschritte,

s.o.

[mar io (Gast)]

Zahnfee schrieb:
> Peter II schrieb:
>> Zahnfee schrieb:
>>> Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z
>>> ist 32.757 dann kommt es zu einem Überlauf.
>>
>> und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit
>> egal sein.
>
> Sollte? LOL. Beweis.

Was ist daran so lustig?

#include <stdio.h>
#include <stdint.h>

int main(int argc, const char * argv[])
{
    int16_t x = 32117;
    int16_t y = 32301;
    int16_t z = 32757;
    
    // 32117, 32301, 32757
    printf("%d, %d, %d\n", x, y, z);
    
    x = x + y + z;
    z = x - y - z;
    y = x - z - y;
    x = x - z - y;

    // 32117, 32301, 32757
    printf("%d, %d, %d\n", z, x, y);
    
    
    return 0;
}

[Zahnfee (Gast)]

mar io schrieb:
> Zahnfee schrieb:
>> Peter II schrieb:
>>> Zahnfee schrieb:
>>>> Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z
>>>> ist 32.757 dann kommt es zu einem Überlauf.
>>>
>>> und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit
>>> egal sein.
>>
>> Sollte? LOL. Beweis.
>
> Was ist daran so lustig?

Das Peter sollte schrieb. Sollte ist kein Beweis.

[mar io (Gast)]

Das Beispiel mit int64_t

#include <stdio.h>
#include <stdint.h>

int main(int argc, const char * argv[])
{
    int64_t x = INT64_MAX - 3;
    int64_t y = INT64_MAX - 7;
    int64_t z = INT64_MAX - 11;
    
    printf("%lld, %lld, %lld\n", x, y, z);
    
    x = x + y + z;
    z = x - y - z;
    y = x - z - y;
    x = x - z - y;

    printf("%lld, %lld, %lld\n", z, x, y);
    
    
    return 0;
}

[(prx) A. K. (prx)]

Peter II schrieb:
> und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit
> egal sein.

Das Verhalten bei Überlauf ist gemäss C Standard offen, wenn es sich um 
Typen mit Vorzeichen handelt. Es sind also auch Saturierung oder 
Exceptions möglich, wenngleich unüblich. Ein Modulo-Verhalten ist nur 
für vorzeichenlose Typen definiert.

[Zahnfee (Gast)]

mar io schrieb:
> Zahnfee schrieb:
>> Peter II schrieb:
>>> Zahnfee schrieb:
>>>> Wenn x, y und z vom Typ int16 sind und x ist 32.117, y ist 32.301 und z
>>>> ist 32.757 dann kommt es zu einem Überlauf.
>>>
>>> und? Der Überlauft ist aber in beide richtungen vorhanden, sollte damit
>>> egal sein.
>>
>> Sollte? LOL. Beweis.
>
> Was ist daran so lustig?

Das Peter sollte schrieb. Sollte ist kein Beweis.

[Mac (Gast)]

Überläufe sind undefiniertes Verhalten und man jede beliebige Reaktion 
auf einen Überlauf ist vom Standard gedeckt.

#include <stdio.h>
#include <limits.h>

int main(int argc, const char * argv[])
{
    int x = INT_MAX-1;
    int y = INT_MAX-2;
    int z = INT_MAX-3;
    printf("%d, %d, %d\n", INT_MAX-x, INT_MAX-y, INT_MAX-z);    
    x = x + y + z;
    z = x - y - z;
    y = x - z - y;
    x = x - z - y;
    printf("%d, %d, %d\n", INT_MAX-x, INT_MAX-y, INT_MAX-z);
    return 0;
}

z.B. Programmabsturz:

$ clang -ftrapv a.c 
$ ./a.out 
1, 2, 3
Illegal instruction (core dumped)

[Jürgen S. (starblue)]

Mit unsigned funktioniert das alles prima, dann sind sowohl Überlauf (es 
wird modulo gerechnet) als auch Bitoperationen wohldefiniert.

In der Praxis sollte man sowas aber lassen und eine temporäre Variable 
nehmen.

[mar io (Gast)]

Ich hab jetzt in einem C Entwurf nach dem Verhalten von Über-/Unterlauf 
bei einer Integer-Rechnung gesucht, aber dazu eigentlich nur gefunden, 
dass das Verhalten undefiniert ist. D.h. der Standard schreibt kein 
konkretes Verhalten vor, aber der Prozessor hat ein bestimmtes 
Verhalten. Somit ist das Verhalten doch gegeben, aber in Abhängigkeit 
vom verwendeten Mikroprozessor.

http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1362.pdf

[Hmm (Gast)]

>ja du hast recht, dann werdens mehr als 4. Dann weis ich auch nicht
>weiter. Des mit dem addieren ist eine gute möglichkeit!

Ich habe Dir doch ausführlich geschrieben, was Du machen sollst. Nicht 
einfach nur einen Schritt machen und dann fragen wenn die Lösung nicht 
winkend und grinsend mit einem Schild in der Hand dasteht um Dich 
abzuholen. Probieren, überlegen, Phantasie walten lassen.

Willst Du Dir immer alles vorsagen lassen?

[(prx) A. K. (prx)]

mar io schrieb:

> Ich hab jetzt in einem C Entwurf nach dem Verhalten von Über-/Unterlauf
> bei einer Integer-Rechnung gesucht, aber dazu eigentlich nur gefunden,
> dass das Verhalten undefiniert ist.

Such dort mal nach der Definition von "undefined". Die schliesst nämlich 
"unpredictable" mit ein.

> D.h. der Standard schreibt kein
> konkretes Verhalten vor, aber der Prozessor hat ein bestimmtes
> Verhalten. Somit ist das Verhalten doch gegeben, aber in Abhängigkeit
> vom verwendeten Mikroprozessor.

Das wäre "unspecified", und zudem noch abhängig vom Compiler.

[Mac (Gast)]

mar io schrieb:
> Ich hab jetzt in einem C Entwurf nach dem Verhalten von Über-/Unterlauf
> bei einer Integer-Rechnung gesucht, aber dazu eigentlich nur gefunden,
> dass das Verhalten undefiniert ist. D.h. der Standard schreibt kein
> konkretes Verhalten vor, aber der Prozessor hat ein bestimmtes
> Verhalten.

Der Compiler entscheidet was der Prozessor macht.

> Somit ist das Verhalten doch gegeben, aber in Abhängigkeit
> vom verwendeten Mikroprozessor.

NEIN. Undefiniertes Verhalten heisst, dass alles mögliche passieren 
kann. Der Compiler kann z.B. davon ausgehen, dass der Überlauf niemals 
stattfindet und den Code denentsprechend optimieren.

Aktuell z.B. hat gcc 4.8.0 eine Optimierung, bei der ein SPEC Benchmark 
wegen undefiniertem Verhalten kaputt geht:

http://blog.regehr.org/archives/918

[Yalu X. (yalu) (Moderator)]

C-Progammer hat übrigens noch vergessen zu schreiben, dass die drei
Variablen vom Typ double sind ;-)

[Zahnfee (Gast)]

Yalu X. schrieb:

> C-Progammer hat übrigens noch vergessen zu schreiben, dass die drei
> Variablen vom Typ double sind ;-)

double hält besser :)

[Rolf M. (rmagnus)]

mar io schrieb:
> Ich hab jetzt in einem C Entwurf nach dem Verhalten von Über-/Unterlauf
> bei einer Integer-Rechnung gesucht, aber dazu eigentlich nur gefunden,
> dass das Verhalten undefiniert ist.

Dazu kommt noch, daß es laut Norm bei unsigned keinen Überlauf gibt.

> D.h. der Standard schreibt kein konkretes Verhalten vor, aber der
> Prozessor hat ein bestimmtes Verhalten. Somit ist das Verhalten doch
> gegeben, aber in Abhängigkeit vom verwendeten Mikroprozessor.

Das Verhalten kann sich aber z.B. auch unterscheiden zwischen 
Rechnungen, die durch den Optimizer zur Compilezeit gemacht werden 
können und solchen, die zur Laufzeit durchgeführt werden. "undefined" 
bedeutet unter anderem auch, daß sich der Compiler nicht um solche 
Unterschiede kümmern muß.

[mar IO (Gast)]

Mac schrieb:
> Aktuell z.B. hat gcc 4.8.0 eine Optimierung, bei der ein SPEC Benchmark
> wegen undefiniertem Verhalten kaputt geht:
>
> http://blog.regehr.org/archives/918

"GCC pre-4.8" - Soweit ich das verstanden habe, hat der GCC 4.8 bei 
'-O2' den Fehler nicht (mehr) und die Zeile

for (dd=d[k=0]; k<16; dd=d[++k]) {     int d[16];

greift auf den Speicher nach dem Array, was gut gehen kann oder auch 
nicht. Der Wert wird nicht verarbeitet, aber der Zugriff auf den 
Speicher ist halt ausserhalb des Arrays. Wieso die Optimierungsstufe 
jetzt da eine Endlosschleife gemacht hat, habe nicht ganz verstanden...

Mac schrieb:
> NEIN. Undefiniertes Verhalten heisst, dass alles mögliche passieren
> kann.

NEIN - würde ich wo nicht sagen. Undefiniert heißt, es wurde nicht 
definiert. "Alles mögliche" kann nicht passieren, sondern das was der 
Compiler (in Verbindung mit der Zielmaschine) daraus macht.

[Mac (Gast)]

Der Compiler geht davon aus, dass die Zugriffe über k nur innerhalb von 
d[] stattfinden (weil der Zugriff ausserhalb ja undefiniertes Verhalten 
wäre) und folgert, dass wenn auf d zugegriffen wird, k nur einen Wert 
zwischen 0 und 15 haben kann und dass dies überdies auch gilt wenn k<16 
abgefragt wird. Aha! sagt er, Endlosschleife ohne Nebeneffekt, kann in 
einen jmp optimiert werden.

GCC hat nun mal recht in der Sache und kann die Schleife so kompilieren 
wie es lustig ist. Und zum Thema was alles passieren kann, google mal 
nach "nasal demons"

[(prx) A. K. (prx)]

Ja, dieses Beispiel ist wirklich gut. Denn man sieht man schön, was für 
Konsequenzen undefiniertes Verhalten haben kann, wenn man es bis zu Ende 
denkt. Und die Compiler denken eben immer weiter und tiefer.

Oftmals hat man im Kopf, dass Überlaufverhalten für einen selbst im 
konkreten Programm doch irrelevant ist, weil x86/ARM/... sowieso modulo 
rechnet, auch wenns nicht definiert ist. Und dann passiert dir so etwas 
wie in diesem Beispiel und der Compiler dreht dir trotzdem eine Nase.

Angesichts der Popularität von GCC im Controller-Umfeld werden wohl 
nicht nur SPECmarks und Linux-Kernels auf die Nase fliegen, wenn die 
Leute wagemutig genug sind, ihr althergebrachtes Programm durch -O3 zu 
schleusen.

[Rolf M. (rmagnus)]

mar IO schrieb:
> Mac schrieb:
>> NEIN. Undefiniertes Verhalten heisst, dass alles mögliche passieren
>> kann.
>
> NEIN - würde ich wo nicht sagen.

Was du sagen würdest, ist aber nicht normativ.

********************************************************************
3.4.3
undefined behavior
behavior, upon use of a nonportable or erroneous program construct or of 
erroneous data, for which this International Standard imposes no 
requirements

NOTE
Possible undefined behavior ranges from ignoring the situation 
completely with unpredictable results, to behaving during translation or 
program execution in a documented manner characteristic of the 
environment (with or without the issuance of a diagnostic message), to 
terminating a translation or execution (with the issuance of a 
diagnostic message).
EXAMPLE
An example of undefined behavior is the behavior on integer overflow.
********************************************************************

Lustigerweise wird hier als Beispiel gerade das hier diskutierte Thema 
genannt.

> Undefiniert heißt, es wurde nicht definiert.

Es heißt, daß die C-Spezifikation keinerlei Vorgaben macht, was ab der 
Stelle, wo undefiniertes Verhalten hervorgerufen wurde, passieren soll. 
Der Compiler-Hersteller darf selbst ein Verhalten definieren oder aber 
den Fall komplett ignorieren, ohne weiter darüber nachzudenken, was dann 
passiert.

> "Alles mögliche" kann nicht passieren, sondern das was der Compiler (in
> Verbindung mit der Zielmaschine) daraus macht.

Nun, in irgendeiner Form nachvollziehbar ist das, was dann passiert, in 
der Regel schon. Aber es ist oft nicht so einfach, wie man auf den 
ersten Blick denkt, und es lauern jede Menge Fallen, die bei einem 
anderen Compiler oder auch (wie hier) der nächsten Compiler-Version oder 
anderen Compiler-Flags schon wieder ganz anders aussehen können. Wenn du 
also nicht den Hauptteil deiner Zeit mit der Analyse des vom Compiler 
erzeugten Code verbringen willst, ist "alles mögliche" eine hinreichend 
genaue Beschreibung dessen, was passieren kann.

[mar IO (Gast)]

Mac schrieb:
> Der Compiler geht davon aus, dass die Zugriffe über k nur innerhalb von
> d[] stattfinden (weil der Zugriff ausserhalb ja undefiniertes Verhalten
> wäre) ...

Japp, das steht auch so in dem Text drinnen. Für mich ist das auch 
nachvollziehbar, aber irgendwie auch nicht...

Jetzt habe ich das probiert aus dem Entwurf rauszulesen, aber 
nachvollziehen kann ich das nicht. Vllt. verstehe ich auch den Text 
nicht??? Es müsste in den Punkten '6.5.2.1 Array subscripting' und 
'6.5.6 Additive operator' Absatz 8 stehen.

Rolf Magnus schrieb:
> Lustigerweise wird hier als Beispiel gerade das hier diskutierte Thema
> genannt.

Es ja echt lustig!

Rolf Magnus schrieb:
>> "Alles mögliche" kann nicht passieren, sondern das was der Compiler (in
>> Verbindung mit der Zielmaschine) daraus macht.
>
> Nun, in irgendeiner Form nachvollziehbar ist das, was dann passiert, in
> der Regel schon. ... Wenn du
> also nicht den Hauptteil deiner Zeit mit der Analyse des vom Compiler
> erzeugten Code verbringen willst, ist "alles mögliche" eine hinreichend
> genaue Beschreibung dessen, was passieren kann.

Ja, da hast Du recht. Ich wollte eigentlich auf das hinaus, dass man zum 
Teil das ganz gut nachvollziehen kann. Wenn man wiederverwendbaren Code 
auf verschiedenen Maschinen mit verschiedenen Compiler erstellen möchte, 
dann sollte man sich nicht auf sowas einlassen.

[Läubi .. (laeubi)]

Undefiniert hin oder her, man sieht hier vor allem wie man sich durch 
"genialen" Code wunderbar selbst ins Bein schießen kann... sogar nach 
Jahren.
Eine Zeile mehr und das Problem wäre passe...

for (k=0; k<16; k++) {
    dd = d[k];
    satd += (dd < 0 ? -dd : dd);
}

... oder ist das Teil des Benchmarks? Kann ja eigentlich nicht sein, da 
der Compiler das ja auch noch optimiert.

[Xenu (Gast)]

Was bezweckt der Dozent eigentlich mit dieser Schwachsinnsaufgabe?
Das die Studenten möglichst komplizierten, fehleranfälligen und 
unverstehbaren Code produzieren lernen?

Am Schönsten finde ich, das der Compiler (gcc) den kürzesten Code 
erzeugt, wenn man die einfachste Methode (temporäre Variable) benutzt.

[Robert L. (lrlr)]

>Was bezweckt der Dozent eigentlich mit dieser Schwachsinnsaufgabe?

ich Programmier jetzt seit  30 Jahren
den "trick" dass man 2 variablen, auch ohne temporäre tauschen kann, 
kannte ich nicht..

die aufgabe dient wohl dazu, dass man es sich merkt (weil man selber 
drüber nachdenken muss)

dass es eher nicht praxisrelevant ist, ist ja bei Grundlagen (boolsche 
operationen) wohl generell eher normal..

[Läubi .. (laeubi)]

Sowas hatten wir auch im Studium (allerdings auf ASM), hauptsächlich 
wird damit "bezweckt", dass man sich einfach mal etwas näher mit der 
Funktion von Operatoren auf Binärebene auseinandersetzt, ein Studium ist 
kein Programmierkurs!

Robert L. schrieb:
> den "trick" dass man 2 variablen, auch ohne temporäre tauschen kann
Mach dir nix draus, der Trick ist auch eher gefährlich da er halt nicht 
immer funktioniert und eher das verhalten verschleiert als verbessert.
Wenn es geht kann das auch der Compiler, und eventuell hat die CPU sogar 
einen swap Befehl der besser ist als zwei lese/schreib Operationen...