[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

簡介C語言volatile關鍵字及其陷阱

volatile變數代表其所儲存的內容會不定時地被改變，宣告volatile變數用來告訴編譯器 (Compiler) 不要對該變數做任何最佳化操作，凡牽涉讀取該volatile變數的操作，保證會到該變數的實體位址讀取，而不會讀取CPU暫存器的內容 (提升效能) 。舉個例子，某一硬體狀態暫存器 (Status Register)就必須宣告volatile關鍵字，因為該狀態暫存器會隨時改變，宣告volatile便可確保每次讀取的內容都是最新的。

Volatile關鍵字的應用範疇

1. 硬體暫存器，如狀態暫存器。
2. 多執行緒所共用的全域變數。
3. 中斷服務函式 (Interrupt Service Rountie，ISR)所使用的全域變數。

Volatile陷阱
想想底下範例是否有問題?

#include <stdio.h>



int square(volatile int *var)

{

    return *var **var;

}



int main(void)

{

    int    var = 5;



    printf("result: %d\n", square(&var));

    return 0;

}

其問題在於square函式的平方算式，*var**var，此指令代表到var位址讀取其內容。然而，var位址可能儲存硬體暫存器，這些暫存器內容會隨時間而改變 (例如: 狀態暫存器)，有可能第一次讀取的時候為4, 下一次讀取為5, 導致計算出來的值不正確。

因此，避免此錯誤發生便是在square函式宣告一local變數，看底下程式範例較為清楚:

#include <stdio.h>



int square(volatile int *var)

{

    int    local_var = *var;



    return local_var * local_var;

}



int main(void)

{

    int    var = 5;



    printf("result: %d\n", square(&var));

    return 0;

}

【Reference】
[1] How to Use C's volatile Keyword

[Linux Kernel] Allocate memory buffer whose starting address is aligned with the specific memory size

撰寫裝置驅動程式時, 常常會因為硬體需求, 需配置一塊記憶體空間用來映射至硬體的I/O或記憶體空間, 且此已配置記憶體空間的起始位址往往都必須對齊某一固定大小的記憶體。舉例來說，欲配置4906位元的記憶體空間，且起始位址需對齊16位元。底下為C語言範例程式。

void *memory_align(unsigned int size, unsigned int aligned_size)

{

    void *ptr;



    unsigned int mask = ~(aligned_size -1);



    if((ptr = malloc(sizeof(size + (aligned_size - 1)))) == NULL) {

        perror("memory allocation failed");

        return NULL;

    }



    ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);



    return ptr;

}

unsigned int mask = ~(aligned_size -1);

此mask變數為位元遮罩, 假設aligned_size=16, 則mask=0xFFFFFFF0。

ptr = malloc(sizeof(size + (aligned_size - 1)))

由於我們欲讓所配置的記憶體起始位址對齊aligned_size, 所以需向系統配置size+(aligned_size - 1)大小的記憶體空間。

ptr = (void *) ((unsigned int) (ptr + (aligned_size - 1)) & mask);

把所配置的記憶體起始位址加上(aligned_size - 1)，然後跟mask變數做位元遮罩，如此便能取得正確的記憶體起始位址。

下圖為詳細範例計算

範例程式下載