交換變數值

以下是一些交換變數值的方法。

C++ 中交換 2 變數常使用：std::swap

若要自己設計 swap 的話，
一種簡單、正確、且速度最快的寫法是：

template <typename T>
    inline void swap (T& a, T& b)
    {
        T t(a); a=b; b=t;
    }

C 語言中，若想支援各種類型的變數交換，
一個 (不是很好的) 方法是：

#define SWAP(T,a,b) {T t=a; a=b; b=t;}

驗證：

int main ()
{   
    float a=-88, b=57;   
    SWAP (float, a, b);
    printf ("\n a=%f  b=%f", a, b);

    char *c="alcohol", *d="water";   
    SWAP (char*, c, d);
    printf ("\n c=%s  d=%s", c, d);
}

除此之外，就只能老實將型別寫出來：

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

不過上面的寫法在 compiler 未最佳化前，
其實多浪費了兩個堆疊空間 (用來傳參數)。


若僅針對 4Bytes 型別做交換 (如char、float 與 int)，
又想寫個「通用」的 swap，一種有趣的寫法是：

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

他的未最佳化組語有點長：

    int t = *(int*)a;      mov   eax,dword ptr [a]
                           mov   ecx,dword ptr [eax]
                           mov   dword ptr [t],ecx
    *(int*)a = *(int*)b;   mov   eax,dword ptr [a]
                           mov   ecx,dword ptr [ b ]
                           mov   edx,dword ptr [ecx]
                           mov   dword ptr [eax],edx
    *(int*)b = t;          mov   eax,dword ptr [ b ]
                           mov   ecx,dword ptr [t]
                           mov   dword ptr [eax],ecx

驗證：

int main ()
{   
    float a=-88.5, b=57.12;
    swap2 (&a, &b);
    printf ("\n a=%f  b=%f", a, b);

    char c='5', d='9';
    swap2 (&c, &d);
    printf ("\n c=%c  d=%c", c, d);
}

不調用函式的情況下，針對 1~4Bytes 型別，
非 MMX 之 x86 組語最快的寫法或許是：

    __asm {                               
        mov  eax, a               
        mov  ebx, b               
        mov  b  , eax               
        mov  a  , ebx               
    }

比較短，但慢些的寫法：
(因為 xchg 指令週期一般比 mov 慢好幾倍)

    _asm {
        mov  eax, a
        xchg eax, b
        mov  a  , eax
    }

同樣短，但更慢：

    _asm {              
        xchg  a, eax     
        xchg  b, eax     
        xchg  a, eax     
    }

比較慢，又額外浪費堆疊空間的寫法是：

    _asm{
        push  a
        push  b
        pop   a
        pop   b
    }

或是浮點數專用的：

    _asm{
        fld   a
        fld   b
        fstp  a
        fstp  b
    }    
  

是否存在不使用額外變數，而能將變數值正確交換的方法呢？
理論上是...... 沒有。但存在一些限制性的做法：

    a ^= b ^= a ^= b;            (1)
    a -= b = (a+=b) - b;         (2)
    a -= b += a -= b = -b;       (3)
    a = a+b, b = a-b, a = a-b;   (4)
    a *= b, b = a/b, a /= b;     (5)

(2)(3)(4) 其實是相同的邏輯。
當 a 和 b 指向相同位址時，以上均得出 0。
(2)~(5) 都有可能發生 over/under flow，
此外，(5) 還有除零導致程式掛掉的問題。

交換「整個」陣列時，一般會先用指標代表原先陣列，
因此，只需交換「代表它」的指標，就能達成陣列的交換。
即使陣列長度不同，也能成功「交換」。

例如：

//原始陣列
int A[] =  { ... };     
int B[] =  { ... };

//用指標代表某個陣列
int * a = A;
int * b = B;

//交換所代表的陣列
int *t = a; a = b; b = t;

於是在 C 中可以這樣設計：

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

void show (void* a, int n)
{
    int i, *p = (int*) a;          //此處強制定成 int
    for (i=0; i<n; ++i)
        printf (" %d", p[i]);
    puts ("");
}

int main()
{
    const int NUM = 8;
    int i; 
    int A[NUM] = {1,2,3,4,5,6,7,8};
    int B[NUM] = {11,12,13,14,15,16,17,18};

    void* a = A;
    void* b = B;

    show (a, NUM);
    show (b, NUM);

    swap (&a, &b);

    show (a, NUM);
    show (b, NUM);
}

更一般化地，我們可用 Widget 模式包覆在非基本類型上，
於是交換 2 個 Widget 時，只要交換其中的物件指標，便可達成物件交換。

把單個或多個元素，從某個起始位址「整批」移到另個位址，
有 2 種情況：
陣列間元素的「部分」抽換，使用 memcpy。
陣列內元素的「自身抽換」，使用 memmove。

自身抽換之元素位於頭尾時，便形成自旋：

void show (int* a, int n)
{
    for (int i=0; i<n; ++i)
        printf (" %d", a[i]);
    puts ("");
}

void left_rotate (int* a, int n)
{
    int t = a[0];
    memmove (a, a+1, (n-1) * sizeof(int));
    a[n-1] = t;
}

int main()
{
    const int NUM = 8;
    int i=3, a[NUM] = {1,2,3,4,5,6,7,8};
    
    while (i--)
        left_rotate (a, NUM), show (a, NUM);
}