[C語言] 兩變數內容值互換技巧

記得大學時, C語言課程一定會談到兩變數內容值互換技巧, 其方法利用暫存空間實現, 如底下程式碼所示:

void swap(int *a, int *b)

{

  int tmp;



  tmp = *a;

  *a = *b;

  *b = tmp;                                                                                             

}

然而, 有幾個方法不使用暫存空間便能達到此目的.

方法一 使用三次互斥或 (Exclusive OR, XOR)

void swap(int *a, int *b)

{

  if(*a != *b) {

      *a = *a ^ *b;

      *b = *a ^ *b;

      *a = *a ^ *b;

  }

}

演算式如下所示:


簡化上段程式碼: 試想底下程式碼有沒有什麼問題?

#include <stdio.h>                                                      



void swap(int *a, int *b)

{

  if(*a != *b)

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

}



int main(void)

{

  int a = 11, b = 3;



  printf("===== before swapping =====\n");

  printf("a: %d, b: %d\n", a, b);



  swap(&a, &b);



  printf("===== after swapping =====\n");

  printf("a: %d, b: %d\n", a, b);



  return 0;

}

直接看執行結果:


為什麼會這樣呢? 筆者將此C程式碼用gcc編譯成組合語言, 用以了解其運作邏輯, 底下為swap函式片段程式碼, 完整組合語言程式碼請按此連結下載.

程式堆疊示意圖

程式說明:

由於使用一行程式碼做三次XOR, gcc編譯器會先把*a, *b, *a, *b的內容放在edx(11), ecx(3), ebx(11), eax(3)暫存器 (line 9-16), 然後再分別對這四個暫存器做三次的XOR:

• line 18-20: 第一次XOR (eax=3 XOR ebx=11), 並將其結果 (ebx=8)回存到變數a的記憶體位址, 如下圖所示:
• line 21-25: 第二次XOR (eax=8 XOR ecx=3), 並將其結果 (ecx=11)回存到變數b的記憶體位址, 如下圖所示:
• line 26-30: 第三次XOR (eax=11 XOR edx=11), 並將其結果 (edx=0)回存到變數a的記憶體位址, 如下圖所示:

所以問題在於, 程式設計師不能在一行程式碼中, 對同一變數做兩次的運算, 否則會造成不可預知的結果, 切記!

方法二 使用加減法

void swap(int *a, int *b)

{

  if(*a != *b) {

      *a = *a + *b;

      *b = *a - *b;

      *a = *a - *b;

  }

}

演算式如下所示:

【Reference】
[1] XOR - the magic swap
[2] XOR swap