Wie könnte man die swap() Funktion einfacher gestalten?

skullyan

Bei einem C++-Tutorial war es Aufgabe, die swap()-Funktion zu schreiben. Dabei war alles bis aufden Inhalt der Funktion so zu übernehmen. Wie könnte man das besser lösen?

#include <iostream>

void swap(int* a, int* b) {
  int c = 0;
  c = *a;
  *a = *b;
  *b = c;
}

int main(int argc, const char *argv[]) {
  int a;
  int b;

  std::cout << "Please enter a and b: ";
  std::cin >> a >> b;
  swap(&a,&b);
  std::cout << "After the swap, a = " << a << ", b = " << b << std::endl;
  std::cin.sync();
  std::cin.get();
}

skullyan schrieb:

Dabei war alles bis aufden Inhalt der Funktion so zu übernehmen.

Dann geht es nicht besser. Es gibt zwar noch ein bis zwei andere Möglichkeiten ohne temporäre Variable, aber die sind nicht vorteilhafter als ein normaler Tausch.

Nexus

Keine sinnlose Initialisierung mit 0 wäre ein Anfang. Auch wenn es hier nicht unbedingt viel ausmacht, solltest du dir solche Dinge abgewöhnen.

skullyan

@Z: Wie wären die denn? @Nexus: Jo, hab ich auch grad gemerkt...

unskilled

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?) gleich schnell - kein Plan, ob es überhaupt irgendwelche Vorteile hat - aber es geht halt :D)

void swap(int* a, int* b) {
  int c = 0;
  c = *a;
  *a = *b;
  *b = c;
}

->

void swap(int* a, int* b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

aber das wird dein compiler eh schon optimiert haben...
a, b, c sind im übrigen sehr hässliche namen...
normalerweise nimmt man lhs und rhs(left/right hand side).
den fkt.-name finde ich auch sehr verwirrend... aber wenn das in deinem buch so gewollt ist, dann wird das sicherlich einen sinn haben...

bb

Nexus

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?) gleich schnell - kein Plan, ob es überhaupt irgendwelche Vorteile hat - aber es geht halt :D)

XOR ist wahrscheinlich langsamer und vor allem weniger generisch. Der "Vorteil": Man braucht keine temporäre Variable. Interessant, dass die Möglichkeit besteht, aber praktisch ist der Ansatz nicht besonders relevant.

Ich habe statt XOR auch mal eine Version mit + und - gesehen.

skullyan

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?) gleich schnell - kein Plan, ob es überhaupt irgendwelche Vorteile hat - aber es geht halt :D)
void swap(int* a, int* b) {
  int c = 0;
  c = *a;
  *a = *b;
  *b = c;
}
->
void swap(int* a, int* b) {
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
aber das wird dein compiler eh schon optimiert haben...
a, b, c sind im übrigen sehr hässliche namen...
normalerweise nimmt man lhs und rhs(left/right hand side).
den fkt.-name finde ich auch sehr verwirrend... aber wenn das in deinem buch so gewollt ist, dann wird das sicherlich einen sinn haben...

bb

Über 3 Xor's? Zeig mal

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?)

Etwa so

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

unskilled

Nexus schrieb:

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?) gleich schnell - kein Plan, ob es überhaupt irgendwelche Vorteile hat - aber es geht halt :D)

XOR ist wahrscheinlich langsamer und vor allem weniger generisch. Der "Vorteil": Man braucht keine temporäre Variable. Interessant, dass die Möglichkeit besteht, aber praktisch ist der Ansatz nicht besonders relevant.

Gut - das wollte ich damit sagen^^
Das es langsamer ist, glaube ich allerdings auch nicht so recht... Imho braucht mov- und xor- befehl gleich viele takte...

@s.:
wie wärs mti ein wenig eigeninitiative?
http://en.wikipedia.org/wiki/XOR_swap_algorithm

bb

unskilled schrieb:

Das es langsamer ist, glaube ich allerdings auch nicht so recht... Imho braucht mov- und xor- befehl gleich viele takte...

Beim Tausch hast du nur drei Zuweisungen, beim XOR-Swap aber drei Zuweisungen und drei XORs.

hustbaer

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?) gleich schnell - kein Plan, ob es überhaupt irgendwelche Vorteile hat - aber es geht halt :D)

hihi ja die XOR geschichte. vollkommen uninteressant heutzutage, und trotzdem fragen es sogar z.t. leute beim vorstellungsgespräch. angeblich. was man im internet nicht so alles liest. könnte mich zerkugeln.

was ich aber eigentlich sagen wollte: wenn ich prüfer wäre, und einer meiner prüflinge würde das mit zeigern machen, dann würde ich ihm gleich mal hübsch 0 punkte auf das beispiel geben.
ist nämlich UB.
grund: du darfst keine werte in zeiger-variablen laden, die kein gültiger zeiger sind.
ist zwar eine dieser einschränkungen im standard die kaum irgendwo relevant sind, aber ist so, und deswegen macht man es nicht

hustbaer schrieb:

hihi ja die XOR geschichte. vollkommen uninteressant heutzutage, und trotzdem fragen es sogar z.t. leute beim vorstellungsgespräch.

Vorstellungsgespräch für was?

hustbaer schrieb:

was ich aber eigentlich sagen wollte: wenn ich prüfer wäre, und einer meiner prüflinge würde das mit zeigern machen, dann würde ich ihm gleich mal hübsch 0 punkte auf das beispiel geben.
ist nämlich UB.
grund: du darfst keine werte in zeiger-variablen laden, die kein gültiger zeiger sind.

Er benutzt die Zeiger als Zeiger. Das ist schon in Ordnung.

hustbaer

Z schrieb:

hustbaer schrieb:

hihi ja die XOR geschichte. vollkommen uninteressant heutzutage, und trotzdem fragen es sogar z.t. leute beim vorstellungsgespräch.

Vorstellungsgespräch für was?

Programmierer-Jobs.

hustbaer schrieb:

was ich aber eigentlich sagen wollte: wenn ich prüfer wäre, und einer meiner prüflinge würde das mit zeigern machen, dann würde ich ihm gleich mal hübsch 0 punkte auf das beispiel geben.
ist nämlich UB.
grund: du darfst keine werte in zeiger-variablen laden, die kein gültiger zeiger sind.

Er benutzt die Zeiger als Zeiger. Das ist schon in Ordnung.

Was der OP macht ist vollkommen OK, sorry falls das falsch rüberkam.

Ich meinte wenn einer einen XOR-Tausch mit Zeigern machen würde.
Mal ganz davon abgesehen dass man dazu sowieso wild rumcasten müsste, da ^ ja nicht auf Zeiger definiert ist.

Und was die Speed angeht: bei CISC CPUs kannst du oft XOR direkt memory/memory machen. Damit brauchst du nur 3x XOR und kein einziges MOV. Auf einem RISC wäre ein XOR Tausch dagegen vollkommen sinnlos, wenn die Werte im Speicher stehen. XOR Tausch verwendet man aber eher wenn die Werte im Register stehen, und man keines pushen/poppen will.

hustbaer schrieb:

Z schrieb:

hustbaer schrieb:

hihi ja die XOR geschichte. vollkommen uninteressant heutzutage, und trotzdem fragen es sogar z.t. leute beim vorstellungsgespräch.

Vorstellungsgespräch für was?

Programmierer-Jobs.

Wohl als Assembler-Programmierer

hustbaer schrieb:

Und was die Speed angeht: bei CISC CPUs kannst du oft XOR direkt memory/memory machen. Damit brauchst du nur 3x XOR und kein einziges MOV. Auf einem RISC wäre ein XOR Tausch dagegen vollkommen sinnlos...

Sehe ich ähnlich, deshalb ist der XOR-Tausch fast immer sinnlos. Ausser man möchte die temporäre Variable sparen.

hustbaer

Z schrieb:

hustbaer schrieb:

Z schrieb:

hustbaer schrieb:

hihi ja die XOR geschichte. vollkommen uninteressant heutzutage, und trotzdem fragen es sogar z.t. leute beim vorstellungsgespräch.

Vorstellungsgespräch für was?

Programmierer-Jobs.

Wohl als Assembler-Programmierer

Nö, das ist ja das krasse! Hab den Link leider nimmer im Kopf, aber das waren schon Hochsprachen-Jobs.

hustbaer schrieb:

Und was die Speed angeht: bei CISC CPUs kannst du oft XOR direkt memory/memory machen. Damit brauchst du nur 3x XOR und kein einziges MOV. Auf einem RISC wäre ein XOR Tausch dagegen vollkommen sinnlos...

Sehe ich ähnlich, deshalb ist der XOR-Tausch fast immer sinnlos. Ausser man möchte die temporäre Variable sparen.

Naja, weshalb sollte man die temporäre Variable sparen wollen? Kostet ja nix.

Z schrieb:

unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?)

Etwa so
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;

was passiert wenn *a==*b das sollte evtl. vorher mal geklärt werden denn sonst hast nen bug der so gut wie unsichtbar ist

lg lolo

noobLolo schrieb:

Z schrieb:
unskilled schrieb:

es gibt noch einen weg über 3 xor`s (ist also ca.(ganz genau?)

Etwa so
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
was passiert wenn *a==*b das sollte evtl. vorher mal geklärt werden denn sonst hast nen bug der so gut wie unsichtbar ist
lg lolo

Was soll dabei passieren?

Z schrieb:

Was soll dabei passieren?

mach ein proggie compilier das und schau nach, das nennt sich dann learning by doing

noobLolo schrieb:

Z schrieb:

Was soll dabei passieren?

mach ein proggie compilier das und schau nach, das nennt sich dann learning by doing

Also schriftlich, beide 1

a=1, b =1
a = 1 xor 1 = 0
b = 0 xor 1 = 1
a = 0 xor 1 = 1

beide 0

a=0, b=0
a = 0 xor 0 = 0
b = 0 xor 0 = 0
a = 0 xor 0 = 0

Geht doch, oder ist da ein Fehler drin?

noobLolo schrieb:

Z schrieb:

Was soll dabei passieren?

mach ein proggie compilier das und schau nach, das nennt sich dann learning by doing

Du meinst also so?:

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

Sieht für mich ein bisschen paranoid aus...