演算法經典：字串反轉的兩種高效實作（異或法與對調法）

問題定義

原地反轉字串（不配置額外記憶體），要求時間 O(N)、空間 O(1)、碼簡潔可讀。面試常見考點。

方法一：異或交換法

利用 a ^= b ^= a ^= b 無需暫存變數交換兩值。注意：C 標準中 a ^= b ^= a ^= b 為未定義行為（同一序列點多次修改），實務應拆分三句或用暫存變數。下列為安全寫法：

char *reverse_xor(char *str) {
    size_t len = strlen(str);
    for (size_t i = 0, j = len - 1; i < j; ++i, --j) {
        str[i] ^= str[j];
        str[j] ^= str[i];
        str[i] ^= str[j];
    }
    return str;
}

方法二：對調法（暫存變數）

最直觀、無未定義行為風險，編譯器優化後效能相同。

char *reverse_swap(char *str) {
    size_t len = strlen(str);
    for (size_t i = 0, j = len - 1; i < j; ++i, --j) {
        char tmp = str[i];
        str[i] = str[j];
        str[j] = tmp;
    }
    return str;
}

單指標版對調法

char *reverse_single(char *str) {
    size_t len = strlen(str);
    for (size_t i = 0; i < len/2; ++i) {
        char tmp = str[i];
        str[i] = str[len-1-i];
        str[len-1-i] = tmp;
    }
    return str;
}

效能與風格比較

最佳實務建議

1. 優先使用 雙指標對調法：語意清晰、無 UB、編譯器會優化成高效指令。
2. 嵌入式系統極度受限記憶體時，確認編譯器支援後可用異或法（拆三句）。
3. C++ 直接用 std::reverse(begin, end)。
4. 切勿配置新記憶體複製反轉（空間 O(N)），除非原字串為 const 不可修改。

測試主程式

int main() {
    char s1[] = "hello";
    char s2[] = "world";
    printf("xor: %s\n", reverse_xor(s1));
    printf("swap: %s\n", reverse_swap(s2));
    return 0;
}