C Inhalt von 2 Variablen tauschen ohne zwischen speichern

[Walter K. (vril1959)]

Gibt es noch andere Lösungen um den Inhalt ohne Zwischenspeichern
zu tauschen?


#include<stdio.h>

int main()
{
   int x=10;   int y=25;

   x ^= y; y ^= x; x ^= y;

   printf("\n x = %i   y = %i ", x, y);
}

[Vincent H. (vinci)]

Walter K. schrieb:
> Gibt es noch andere Lösungen um den Inhalt ohne Zwischenspeichern
> zu tauschen?
>
>
> #include<stdio.h>
>
> int main()
> {
>    int x=10;   int y=25;
>
>    x ^= y; y ^= x; x ^= y;
>
>    printf("\n x = %i   y = %i ", x, y);
> }

int x = 25; int y = 10;

[Jemand (Gast)]

#define x y
#define y x

Hat sogar überhaupt keine Laufzeitkosten!

[MaWin (Gast)]

Jemand schrieb:
> #define x y
> #define y x

1. April ist vorbei.

[Hanns (Gast)]

In 
[[https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd]] 
wird es mit Addition und Subtraktion gezeigt.

[Walter K. (walter_k488)]

Jemand schrieb:
> #define x y
> #define y x
>
> Hat sogar überhaupt keine Laufzeitkosten!

Ah - ein Experte!

[Nop (Gast)]

Hanns schrieb:
> In
> [[https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd]]
> wird es mit Addition und Subtraktion gezeigt.

Wobei das nur für unsigned int definiert ist und bei signed int 
undefined behaviour.

[mh (Gast)]

Hanns schrieb:
> In
> [[https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd]]
> wird es mit Addition und Subtraktion gezeigt.

If you enable overflows exceptions, then pass unsigned values so an exception isn't thrown.

Wenn man diese Variante für signed integer benutzt möchte, sollte man 
vorher nach unsigned casten, damit man kein undefined sondern 
implementation defined behavior hat. Oder besser gleich die xor Variante 
nehmen die für signed und unsigned geeignet ist.

Don't use this with floating-point numbers (unless you operate on their raw integer representations).

Was ist die raw integer representation eines floats?

[Jemand (Gast)]

mh schrieb:
> Was ist die raw integer representation eines floats?

Das, was du bekommst, wenn du per Union eine Gleitkommazahl als Integer 
interpretierst.

[Sebastian (Gast)]

Warum?

Offensichtich geht es um C (steht in der Überschrift, und du machst dir 
um undefined behaviour Sorgen).
Du weißt also eh nicht, was nach dem Optimieren raus kommt.

Warum nimmst du nicht die am einfachsten zu verstehende Lösung, bei der 
du noch hoffen kannst dass auch der Compiler versteht was du willst, 
weil er das Muster erkennt (mit Zwischenspeichern) und läßt den Compiler 
optimieren?

[zitter_ned_aso (Gast)]

Und wenn die Variablen Strings sind? Oder struct-Variablen?

[zitter_ned_aso (Gast)]

Hier, mal ganz was erstaunliches ;-)

    int x=10;
    int y=20;
    printf("vorher: x=%d, y=%d\n", x,y);

    x=x+y;
    y=x-y;
    x=x-y;

    printf("nachher: x=%d, y=%d\n", x,y);

Ausgabe:

vorher: x=10, y=20
nachher: x=20, y=10

[zitter_ned_aso (Gast)]

und mit Multiplikation/Division ;-)

    int x=10;
    int y=20;
    printf("vorher: x=%d, y=%d\n", x,y);

    x=x*y;
    y=x/y;
    x=x/y;

    printf("nachher: x=%d, y=%d\n", x,y);

[mh (Gast)]

Jemand schrieb:
> mh schrieb:
>> Was ist die raw integer representation eines floats?
>
> Das, was du bekommst, wenn du per Union eine Gleitkommazahl als Integer
> interpretierst.
Soweit ich das sehe ist das legal, wenn man einen unsigned int 
passender Größe nimmt. Interessant.


Sebastian schrieb:
> Warum nimmst du nicht die am einfachsten zu verstehende Lösung, bei der
> du noch hoffen kannst dass auch der Compiler versteht was du willst,
> weil er das Muster erkennt (mit Zwischenspeichern) und läßt den Compiler
> optimieren?
Ich weiß nicht, was der Anlass für diese Frage ist, aber es gibt Fälle 
in denen diese Art der Optimierung notwendig ist, um Register 
einzusparen.

[mh (Gast)]

zitter_ned_aso schrieb:
> Und wenn die Variablen Strings sind? Oder struct-Variablen?
2 unsigned char* + Schleife

[leo (Gast)]

mh schrieb:
> aber es gibt Fälle
> in denen diese Art der Optimierung notwendig ist, um Register
> einzusparen.

Ich denke mal, das braucht mehr Register (4?) als das simple Swap (3) 
(angenommen der Item passt in ein Register).
Warum das herumgeistert ist wohl nur wegen unbekannt und erstaunlich 
Effekten.

leo

[Rolf M. (rmagnus)]

mh schrieb:
> Jemand schrieb:
>> mh schrieb:
>>> Was ist die raw integer representation eines floats?
>>
>> Das, was du bekommst, wenn du per Union eine Gleitkommazahl als Integer
>> interpretierst.
> Soweit ich das sehe ist das legal, wenn man einen unsigned int
> passender Größe nimmt. Interessant.

Nein, man darf immer nur auf das Union-Element zugreifen, das "aktiv" 
ist, und das ist das zuletzt geschriebene.

leo schrieb:
> Ich denke mal, das braucht mehr Register (4?) als das simple Swap (3)

Wofür sollten so viele Register nötig sein?

[leo (Gast)]

Rolf M. schrieb:
>> Ich denke mal, das braucht mehr Register (4?) als das simple Swap (3)
>
> Wofür sollten so viele Register nötig sein?

Ja, sorry - da hab ich wohl geirrt.

leo

[Jemand (Gast)]

Rolf M. schrieb:
> Nein, man darf immer nur auf das Union-Element zugreifen, das "aktiv"
> ist, und das ist das zuletzt geschriebene.

C11 erlaubt das.

6.5.2.3 Structure and union members:

95) If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation.

[mh (Gast)]

Rolf M. schrieb:
> Nein, man darf immer nur auf das Union-Element zugreifen, das "aktiv"
> ist, und das ist das zuletzt geschriebene.

In C erlaubt in C++ verboten (mit Ausnahmem)

[Jobst Q. (joquis)]

zitter_ned_aso schrieb:
> Und wenn die Variablen Strings sind?

Kein Problem. Pointer kann man genauso tauschen wie unsigned int.

[zitter_ned_aso (Gast)]

tja, dann wollt ihr Strings in irgendwelchen Schleifen durchlaufen.

Also kommt eine Laufvariable zum Einsatz. Man hat also doch eine 
zusätzliche Variable.

[Rolf M. (rmagnus)]

zitter_ned_aso schrieb:
> tja, dann wollt ihr Strings in irgendwelchen Schleifen durchlaufen.

Nö, wozu?

[zitter_ned_aso (Gast)]

ja, stimmt. man kann alles per Hand machen

    char str1[10]="hallo";
    char str2[10]="welt";

    printf("vorher: %s %s\n", str1, str2);

    *str1^=*str2;
    *str2^=*str1;
    *str1^=*str2;
    
    printf("1. Durchgang: %s %s\n", str1, str2);

    *(str1+1)^=*(str2+1);
    *(str2+1)^=*(str1+1);
    *(str1+1)^=*(str2+1);

    printf("2. Durchgang: %s %s\n", str1, str2);

    //usw...

[Yalu X. (yalu) (Moderator)]

Ich habe gerade etwas Interessantes festgestellt:

Der GCC erzeugt bei eingeschalteter Optimierung für alle drei Varianten
des folgenden Codes

#include <stdint.h>

#define METH 1

void sub2(uint8_t a, uint8_t b);

void sub1(uint8_t n, uint8_t a, uint8_t b) {
  for(uint8_t i=0; i<n; i++) {
    sub2(a, b);

#if METH==0
    uint8_t tmp = a;
    a = b;
    b = tmp;
#elif METH==1
    a ^= b;
    b ^= a;
    a ^= b;
#elif METH==2
    a -= b;
    b += a;
    a = b - a;
#endif

  }
}

exakt den gleichen Assemblercode. Betrachtet man diesen näher, findet
man darin die folgende Codesequenz (in Pseudoassembler, gilt sowohl für
PC als auch für AVR):

  move reg1 to reg3
  move reg2 to reg1
  move reg3 to reg2

Somit braucht man sich wenigstens nicht den Kopf darüber zu zerbrechen,
welche der drei Methoden die effizienteste (in Bezug auf Laufzeit oder
Speicher) ist :)

[zitter_ned_aso (Gast)]

lol

[Oliver S. (oliverso)]

Yalu X. schrieb:
> Somit braucht man sich wenigstens nicht den Kopf darüber zu zerbrechen,
> welche der drei Methoden die effizienteste (in Bezug auf Laufzeit oder
> Speicher) ist :)

Was dann auch zur (wenig erstaunlichen) allumfassend Antwort auf die 
Eingangsfrage führt:

Gar nicht.

Oliver

[Rolf M. (rmagnus)]

zitter_ned_aso schrieb:
> ja, stimmt. man kann alles per Hand machen

Du hast es immer noch nicht verstanden: Warum soll man die Strings 
iterieren, um zwei Zeiger auszustauschen?

[Jobst Q. (joquis)]

zitter_ned_aso schrieb:
> ja, stimmt. man kann alles per Hand machen

    char *str1 = "hallo";
    char *str2 = "welt";

    printf("vorher: %s %s\n", str1, str2);

    (unsigned long)str1 ^= (unsigned long)str2;
    (unsigned long)str2 ^= (unsigned long)str1;
    (unsigned long)str1 ^= (unsigned long)str2;
    
    printf("nachher: %s %s\n", str1, str2);

[x^y (Gast)]

Walter K. schrieb:
> Gibt es noch andere Lösungen um den Inhalt ohne Zwischenspeichern
> zu tauschen?
>
> #include<stdio.h>
>
> int main()
> {
>    int x=10;   int y=25;
>
>    x ^= y; y ^= x; x ^= y;
>
>    printf("\n x = %i   y = %i ", x, y);
> }

Bester Tipp: Lass den Quatsch, das ist nicht effizienter. Zweitbester 
Tipp: Was passiert denn wenn x und y identisch sind (im Sinne identische 
Variable wenn du das Konstrukt später als Makro oder inline Funktion 
verpackt hast)?

x = y = 42;
 -> x ^= y;
 -> x = x ^ y;
 -> x = x ^ x;
 -> x = 0

[Walter K. (vril1959)]

x^y schrieb:
> Was passiert denn wenn x und y identisch sind

naja .. einfach if(x^y) { /*tausche*/ }

[Thomas M. (langhaarrocker)]

Mit int in C wird das so nix. Allenfalls wenn man die Nibbles eines 
Bytes vertauschen möchte könnte man beispiesweise auf ATMegas inline 
Assembler verwenden um SWAP 
(https://www.microchip.com/webdoc/avrassembler/avrassembler.wb_SWAP.html) 
zu verwenden. Aber das ist dann nicht mehr wirklich C.

[Yalu X. (yalu) (Moderator)]

Walter K. schrieb:
> x^y schrieb:
>> Was passiert denn wenn x und y identisch sind
>
> naja .. einfach if(x^y) { /*tausche*/ }

Dann ist es aber definitiv ineffizienter als die Methode mit der
temporären Variable.

[Niklas G. (erlkoenig)]

Jobst Q. schrieb:
> (unsigned long)str1 ^= (unsigned long)str2;
>     (unsigned long)str2 ^= (unsigned long)str1;
>     (unsigned long)str1 ^= (unsigned long)str2;

Und was wenn "long" nicht groß genug für einen Pointer ist? Wenn schon 
dann "uintptr_t" ...

Alternativ C++ verwenden und std::swap(x,y); aufrufen. Das nutzt 
automatisch den optimalen Weg für den jeweiligen Typ (insb. für 
Strings).

[A. S. (Gast)]

zitter_ned_aso schrieb:
> Hier, mal ganz was erstaunliches ;-)

ja ;-)
Hanns schrieb:
> In
> [[https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesSubAdd]]
> wird es mit Addition und Subtraktion gezeigt.

Wobei XOR ja auch eine Addition ist, nur halt Bitweise und man nicht 
zwischen Addition und Subtraktion unterscheiden muss (daher beides mal 
XOR nehmen kann).

[[K]ein Sohn [des] Admins (frei nach Lk 3,33) (Gast)]

x^y schrieb:
> Walter K. schrieb:
>> Gibt es noch andere Lösungen um den Inhalt ohne Zwischenspeichern
>> zu tauschen?
>>
>> #include<stdio.h>
>>
>> int main()
>> {
>>    int x=10;   int y=25;
>>
>>    x ^= y; y ^= x; x ^= y;
>>
>>    printf("\n x = %i   y = %i ", x, y);
>> }
>
> Bester Tipp: Lass den Quatsch, das ist nicht effizienter. Zweitbester
> Tipp: Was passiert denn wenn x und y identisch sind (im Sinne identische
> Variable wenn du das Konstrukt später als Makro oder inline Funktion
> verpackt hast)?
> x = y = 42;
>  -> x ^= y;
>  -> x = x ^ y;
>  -> x = x ^ x;
>  -> x = 0

Leider seh ich nicht was Du genau meinst. Vielleicht liegt es auch an 
der Optimierung des GCC, allerdings glaube ich das (noch) nicht.

#include<stdio.h>

int main()
{
   int x=25;   int y=25;

   printf("\n x = %i   y = %i ", x, y);

   x ^= y; // x=0

   printf("\n x = %i   y = %i ", x, y);

   y ^= x; // y=25

   printf("\n x = %i   y = %i ", x, y);

   x ^= y; // x=25

   printf("\n x = %i   y = %i ", x, y);
}

% ./a.out 

 x = 25   y = 25 
 x = 0   y = 25 
 x = 0   y = 25 
 x = 25   y = 25

[Niklas G. (erlkoenig)]

[K]ein Sohn [des] Admins (frei nach Lk 3,33) schrieb im Beitrag 
#5797110:
> Leider seh ich nicht was Du genau meinst

Sollte man auf die Idee kommen das Tauschen (hässlich) in ein Makro zu 
packen:

#define UINT_SWAP(x,y) do { (x) ^= (y); (y) ^= (x); (x) ^= (y); } while (0)

und das Makro auf einer Variable mit sich selbst aufrufen (was in 
verschachtelten Konstruktionen schon mal passieren kann):

int main () {
  unsigned int a = 42;
  UINT_SWAP (a, a);
  printf ("%d\n", a);
}

kommt 0 heraus. Mit std::swap ist das kein Problem:

int main () {
  int a = 42;
  std::swap (a, a);
  std::cout << a << std::endl;
}

Das funktioniert übrigens so:

  /**
   *  @brief Swaps two values.
   *  @param  __a  A thing of arbitrary type.
   *  @param  __b  Another thing of arbitrary type.
   *  @return   Nothing.
  */
  template<typename _Tp>
    inline
#if __cplusplus >= 201103L
    typename enable_if<__and_<__not_<__is_tuple_like<_Tp>>,
            is_move_constructible<_Tp>,
            is_move_assignable<_Tp>>::value>::type
    swap(_Tp& __a, _Tp& __b)
    noexcept(__and_<is_nothrow_move_constructible<_Tp>,
              is_nothrow_move_assignable<_Tp>>::value)
#else
    void
    swap(_Tp& __a, _Tp& __b)
#endif
    {
      // concept requirements
      __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)

      _Tp __tmp = _GLIBCXX_MOVE(__a);
      __a = _GLIBCXX_MOVE(__b);
      __b = _GLIBCXX_MOVE(__tmp);
    }

Also der klassische Ringtausch mit temporärer Variable. Wäre interessant 
ob man einen Testfall basteln kann, in dem der Optimizer den Xor-Trick 
nutzt.

[[K]ein Sohn [des] Admins (frei nach Lk 3,33) (Gast)]

Niklas G. schrieb:
> [K]ein Sohn [des] Admins (frei nach Lk 3,33) schrieb im Beitrag
> #5797110:
>> Leider seh ich nicht was Du genau meinst
>
> Sollte man auf die Idee kommen das Tauschen (hässlich) in ein Makro zu
> packen:
> #define UINT_SWAP(x,y) do { (x) ^= (y); (y) ^= (x); (x) ^= (y); } while
> (0)

Danke, jetz seh ichs auch.

[Peter D. (peda)]

Walter K. schrieb:
> Gibt es noch andere Lösungen um den Inhalt ohne Zwischenspeichern
> zu tauschen?

In C kümmert sich der Compiler um die Optimierung und da sollte man ihm 
gefälligst nicht ins Handwerk pfuschen.
In C gilt: Schreib es so hin, wie es am besten lesbar ist.
Irgendwelche dirty Assemblerhacks haben in C-Programmen nichts verloren.