tauschen 2er Variablen ohne Hilfsvariable

[Killswitch]

Er hatte zuerst in "Exotische Programmiersprachen" gepostet. Die haben den Thread dann hierher verschoben.

[Moskito]

Die (oft) beschriebene Lösung geht nur mit ganzzahligen Datentypen!
In jeder Sprache, in der es Zeiger gäbe, wäre es sehr einfach eine für jeden Datentyp passende Lösung zu erstellen. So könntest du in C einfach schreiben:

#include <stdio.h>

int main(int argc, char *argv[])
{
    char *s1="string1";
    char *s2="string2";
    
    printf("%s\n", s1);
    printf("%s\n\n", s2);
    
    s1=(void *)((long)s1^(long)s2);
    s2=(void *)((long)s1^(long)s2);
    s1=(void *)((long)s1^(long)s2);
    
    printf("%s\n", s1);
    printf("%s\n\n", s2);
    getchar();

}

Und das ginge dann mit jedem Datentyp.

In VB musst du dafür tricksen. Das heisst, entweder bildest du in VB Zeiger nach. Damit habe ich ehrlichgesagt aber noch keine Erfahrung gemacht. (http://www.activevb.de/tutorials/tut_zeiger/zeiger.html)
Oder du machst das halt per API, und dann Byte für Byte. Sprich du beschaffst dir direkten Zugriff auf den Prozessspeicher, schaust wo die Variablen liegen, und wieviel Speicher sie brauchen. Dann gehst du Byte für Byte die xor Methode durch. Dazu wirst du zwar einige zusätzliche Variablen brauchen, aber in keiner wird jemals ein Teil der Variablen gespeichert.
Oder, wenn du das einfach für den Datentyp String oder für ganzzahlige Arrays brauchst, dann gehst du beim String einfach in einer For-Schleife Buchstabe für Buchstabe durch, und beim Array Element für Element. (Bei einem Stringarray natürlich gleich beides miteineander gemixt. )

mfg Moskito

[slanger]

Hm also das array ist ein String
hm kann es daran liegen?

[Jesuz]

gibts nich in vb wie in c++ ne swap anweisung?

[ashyak]

@Jesuz

...
Dies soll ohne eine dritte variable und ohne die swap() möglichkeit gehn.
...

die will er doch nicht nutzen.

[Jesuz]

Oh, sorry, habsch net gelesen

wird hoffentlich net wieda vorkommen

[retak]

Hallo,
ich hätte nie gedacht, dass ich mich nach 7 Jahren noch an diesen Thread erinnere (und ihn auch finde). Aber genau die selben Aufgaben muss ich gerade in einer Übung lösen.

Und damit der Nächste nicht suchen muss, hier die Zusammenfassung:

Tausche 2 Variablen ohne 3 Variable

a) nur mit der Addition und Subtraktion:
a = a - b
b = a + b
a = b - a

oder
a = a + b
b = a - b
a = a - b

b) nur mit XOR
a = a^b
b = a^b
a = a^b

Darf man eine 3. Variable benutzen, hat aber nur eine OR Funktion zur Verfügung, geht das so:

c)
c = a OR a
b = a OR a
a = c OR c

Und mit einem Stack geht das so:
b auf den Stack legen
b = a
a = Wert vom Stack holen

Grüße

[gruena]

Hatte mal irgendwo gelesen, dass xor-swap nicht immer funktioniert, und da musste ich das erst eben mit Firebug testen. xD

success = 0;
tests = 0;

for (i=-255; i<255; i++)
    for (j=-255; j<255; j++)
    {
        expectedSwapA = j;
        expectedSwapB = i;

        a = i;
        b = j;

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

        if ((a == expectedSwapA) && (b == expectedSwapB))
            success++;
        tests++;
    }

document.write("success rate: " + success + "/" + tests);

Ausgabe:

success rate: 260100/260100

Shit, tut also doch.

[Moskito]

Mal auf (VB).NET bezogen:

Addition-Subtraktion funktioniert designbedingt nur im Intervall [-DataType.MaxValue/2, DataType.MaxValue/2].
XOR/OR ist zu langsam und funktioniert nur mit Ganzzahltypen.

Um das etwas zu veranschaulichen, folgendes Szenario (ich habe versucht es möglichst "fair" zu gestalten):

Module Module1

    Private Delegate Sub SwapLong(ByRef par1 As Long, ByRef par2 As Long)
    Private Delegate Sub SwapDouble(ByRef par1 As Double, ByRef par2 As Double)

    Sub Main()
        Dim times As Long = 50000000
        Console.WriteLine("Long functions:")
        InvokeFunctionLong(times, AddressOf SwapTemp)
        InvokeFunctionLong(times, AddressOf SwapAddSub)
        InvokeFunctionLong(times, AddressOf SwapXOR)
        InvokeFunctionLong(times, AddressOf SwapTempGeneric(Of Long))
        Console.WriteLine()
        Console.WriteLine("Double functions:")
        InvokeFunctionDouble(times, AddressOf SwapTemp)
        InvokeFunctionDouble(times, AddressOf SwapTempGeneric(Of Double))
        Console.ReadLine()
    End Sub

    Private Sub SwapTemp(ByRef a As Long, ByRef b As Long)
        Dim c As Long
        c = a
        a = b
        b = c
    End Sub

    Private Sub SwapTemp(ByRef a As Double, ByRef b As Double)
        Dim c As Double
        c = a
        a = b
        b = c
    End Sub

    Private Sub SwapAddSub(ByRef a As Long, ByRef b As Long)
        a = a - b
        b = a + b
        a = b - a
    End Sub

    Private Sub SwapAddSub(ByRef a As Double, ByRef b As Double)
        a = a - b
        b = a + b
        a = b - a
    End Sub

    Private Sub SwapXOR(ByRef a As Long, ByRef b As Long)
        a = a Xor b
        b = a Xor b
        a = a Xor b
    End Sub

    Private Sub InvokeFunctionLong(times As Long, ref As SwapLong)
        Dim before As Int64 = CLng(DateTime.Now.Ticks / 10000)

        For i As Long = -times To times
            Dim v1 As Long = i
            Dim v2 As Long = times - i
            ref.Invoke(v1, v2)
        Next

        Dim after As Int64 = CLng(DateTime.Now.Ticks / 10000)
        Console.WriteLine(ref.Method.Name & ", " & times & " times: " & CLng(after - before).ToString & " ms")
    End Sub

    Private Sub InvokeFunctionDouble(times As Long, ref As SwapDouble)
        Dim before As Int64 = CLng(DateTime.Now.Ticks / 10000)

        For i As Long = -times To times
            Dim v1 As Double = i
            Dim v2 As Double = times - i
            ref.Invoke(v1, v2)
        Next

        Dim after As Int64 = CLng(DateTime.Now.Ticks / 10000)
        Console.WriteLine(ref.Method.Name & ", " & times & " times: " & CLng(after - before).ToString & " ms")
    End Sub

    Private Sub SwapTempGeneric(Of T)(ByRef a As T, ByRef b As T)
        Dim c As T
        c = a
        a = b
        b = c
    End Sub

End Module

Resultat (Intel Prozessor SP9600, .NET 4.0):

Long functions:
SwapTemp, 50000000 times: 1009 ms
SwapAddSub, 50000000 times: 1710 ms
SwapXOR, 50000000 times: 1594 ms
SwapTempGeneric, 50000000 times: 1010 ms

Double functions:
SwapTemp, 50000000 times: 2302 ms
SwapTempGeneric, 50000000 times: 2303 ms

Der IL-Code sagt eigentlich schon alles:

  .method private static void  SwapTemp(int64& a,
                                        int64& b) cil managed
  {
    // Code size       11 (0xb)
    .maxstack  2
    .locals init ([0] int64 c)
    IL_0000:  ldarg.0
    IL_0001:  ldind.i8
    IL_0002:  stloc.0
    IL_0003:  ldarg.0
    IL_0004:  ldarg.1
    IL_0005:  ldind.i8
    IL_0006:  stind.i8
    IL_0007:  ldarg.1
    IL_0008:  ldloc.0
    IL_0009:  stind.i8
    IL_000a:  ret
  } // end of method Module1::SwapTemp


  .method private static void  SwapTemp(float64& a,
                                        float64& b) cil managed
  {
    // Code size       11 (0xb)
    .maxstack  2
    .locals init ([0] float64 c)
    IL_0000:  ldarg.0
    IL_0001:  ldind.r8
    IL_0002:  stloc.0
    IL_0003:  ldarg.0
    IL_0004:  ldarg.1
    IL_0005:  ldind.r8
    IL_0006:  stind.r8
    IL_0007:  ldarg.1
    IL_0008:  ldloc.0
    IL_0009:  stind.r8
    IL_000a:  ret
  } // end of method Module1::SwapTemp


  .method private static void  SwapAddSub(int64& a,
                                          int64& b) cil managed
  {
    // Code size       22 (0x16)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  ldarg.0
    IL_0002:  ldind.i8
    IL_0003:  ldarg.1
    IL_0004:  ldind.i8
    IL_0005:  sub.ovf
    IL_0006:  stind.i8
    IL_0007:  ldarg.1
    IL_0008:  ldarg.0
    IL_0009:  ldind.i8
    IL_000a:  ldarg.1
    IL_000b:  ldind.i8
    IL_000c:  add.ovf
    IL_000d:  stind.i8
    IL_000e:  ldarg.0
    IL_000f:  ldarg.1
    IL_0010:  ldind.i8
    IL_0011:  ldarg.0
    IL_0012:  ldind.i8
    IL_0013:  sub.ovf
    IL_0014:  stind.i8
    IL_0015:  ret
  } // end of method Module1::SwapAddSub


  .method private static void  SwapAddSub(float64& a,
                                          float64& b) cil managed
  {
    // Code size       22 (0x16)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  ldarg.0
    IL_0002:  ldind.r8
    IL_0003:  ldarg.1
    IL_0004:  ldind.r8
    IL_0005:  sub
    IL_0006:  stind.r8
    IL_0007:  ldarg.1
    IL_0008:  ldarg.0
    IL_0009:  ldind.r8
    IL_000a:  ldarg.1
    IL_000b:  ldind.r8
    IL_000c:  add
    IL_000d:  stind.r8
    IL_000e:  ldarg.0
    IL_000f:  ldarg.1
    IL_0010:  ldind.r8
    IL_0011:  ldarg.0
    IL_0012:  ldind.r8
    IL_0013:  sub
    IL_0014:  stind.r8
    IL_0015:  ret
  } // end of method Module1::SwapAddSub


  .method private static void  SwapXOR(int64& a,
                                       int64& b) cil managed
  {
    // Code size       22 (0x16)
    .maxstack  8
    IL_0000:  ldarg.0
    IL_0001:  ldarg.0
    IL_0002:  ldind.i8
    IL_0003:  ldarg.1
    IL_0004:  ldind.i8
    IL_0005:  xor
    IL_0006:  stind.i8
    IL_0007:  ldarg.1
    IL_0008:  ldarg.0
    IL_0009:  ldind.i8
    IL_000a:  ldarg.1
    IL_000b:  ldind.i8
    IL_000c:  xor
    IL_000d:  stind.i8
    IL_000e:  ldarg.0
    IL_000f:  ldarg.0
    IL_0010:  ldind.i8
    IL_0011:  ldarg.1
    IL_0012:  ldind.i8
    IL_0013:  xor
    IL_0014:  stind.i8
    IL_0015:  ret
  } // end of method Module1::SwapXOR


  .method private static void  SwapTempGeneric<T>(!!T& a,
                                                  !!T& b) cil managed
  {
    // Code size       27 (0x1b)
    .maxstack  2
    .locals init ([0] !!T c)
    IL_0000:  ldarg.0
    IL_0001:  ldobj      !!T
    IL_0006:  stloc.0
    IL_0007:  ldarg.0
    IL_0008:  ldarg.1
    IL_0009:  ldobj      !!T
    IL_000e:  stobj      !!T
    IL_0013:  ldarg.1
    IL_0014:  ldloc.0
    IL_0015:  stobj      !!T
    IL_001a:  ret
  } // end of method Module1::SwapTempGeneric

Die Sub SwapTempGeneric demonstriert übrigens sehr schön, wie man das in .NET universell mit sehr wenig Code implementieren kann.

mfg Moskito