孟子曰：“尽信《书》，则不如无《书》”

陈硕Muduo一书第12章中提及“用异或交换变量是错误的”。校招面试的时候经常遇到这个问题，竟然没有深入思考这一点。

首先来看看翻转一个字符串的三种方法：

• 方法一：

void reverse_by_swap(char* str, int n) {
  char *b = str;
  char* e = str + n - 1;

  while(b < e) {
    char t = *b;
    *b = *e;
    *e = t;
    ++b;
    --e;
  }
}

• 方法二：

void reverse_by_xor(char* str, int n) {
  char *b = str;
  char* e = str + n - 1;

  while (b < e) {
    *b ^= *e;
    *e ^= *b;
    *b ^= *e;
    ++b;
    --e;
  }
}

• 方法三：

void reverse_by_std(char* str, int n) {
  std::reverse(str, str + n);
}

使用下面程序来测试三种方法耗时：

Timestamp ts;
for (int i = 0; i < 1000000; ++i)
    reverse_by_swap(r, 10);
int64_t t1 = ts.elapsed();

ts.update();
for (int i = 0; i < 1000000; ++i)
    reverse_by_xor(l, 10);
int t2 = ts.elapsed();

ts.update();
for (int i = 0; i < 1000000; ++i)
    std::reverse(s, s+ 10);
int t3 = ts.elapsed();
logger().info("t1=" + std::to_string(t1) + " t2: " + std::to_string(t2) + " t3: " + std::to_string(t3));

测试的字符串分为长字符串和短字符串两种（样例随机选择，能够支持最后结论就好）：

char *str1 = "0123456789";
char *str2 = "012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789";

三种方法的时间耗时如下表，单位纳秒：

字符串	方法一	方法二	方法三
str1	4960	8928	6447
str2	85311	230144	11904

可以看出方法二的复杂度明显高于其他两个方法，以后在面试的时候可以让学生分析为什么会这样。对于方法一和方法三，在字符串较短时方法一更高效，字符串较长时方法三更高效。在网上搜了一圈，没看出std::reverse是怎么实现的。cppreference给出的可能实现如下：

template<class BidirIt>
void reverse(BidirIt first, BidirIt last) {
  while ((first != last) && (first != --last)) {
    std::iter_swap(first++, last);
  }
}

这三种方法的对比得出了几点结论：

• 标准库的实现往往是最佳的选择；
• 深入思考打败人云亦云；
• 没有测试数据作证的揣测都是臆想；
• premature optimization is the root of all evil。