随笔档案

一个字符串由 a - z 26 个字符组成，其中只有一个字符出现的次数为奇数次，其他 25 个字符出现次数都是偶数次。

找出这个出现奇数次的字符。

这个问题，最直观的解法就是遍历一下，记录每个字符的出现次数 int x[26] = {0};

然后扫描 x 检测即可。

但是回过头来想一下这样做有必要吗，看看我们这样做的后果是什么，我们得到了所有字符出现的次数，然后检测以得到出现次数为奇数的字符，这种方法是可以的，但是没有必要得到每个字符的出现次数，也就是说我们得到了大量的冗余信息，这种冗余信息是需要代价的。这也就导致了我们的这种方法效率不高。

把问题认识清楚很重要，最重要。我们只需要找到出现次数为奇数的字符，不需要得到每个字符的具体出现次数。我们可以利用位运算中的异或。

异或的运算性质是：

a ^ a = 0

a ^ a ^ a = a

偶数个本身异或运算为 0

奇数个本身异或运算为其本身

也就是说，我们可以对字符串中的每个字符，一遍扫描，做异或运算，由于 25 个字符出现偶数次，1 个字符出现奇数次，一遍扫描异或运算得到的结果即是出现次数为奇数的那个字符。

总结：
一个问题的解决，要从认清问题开始。求解问题的好的方法是观察我们的解决过程，看看是不是中间得到了冗余的信息，如果存在这种冗余信息，说明我们的解法做了不必要的计算，有更大的改进空间。

异或运算很巧妙。关于它的巧妙运用很多地方都有提到。其中《编程之美》中有关于异或运算的运用。