gcd的递归与非递归实现
欧几里得算法的自然语言描述
计算两个非负整数p和q的最大公约数：若 q 是0，则最大公约数为p。否则，将 p 除以 q 得到余数 r，p和q的最大公约数即为 q 和 r 的最大公约数。
递归实现
根据自然语言描述实现递归的 gcd 算法是比较容易的：
int gcd(int p, int q) {
if (q == 0) {
return p;
}
int r = p % q;
return gcd(q, r);
}
非递归实现
由于递归版本的 gcd 是一个尾递归函数，因此改写为迭代版本的实现相对也较为容易。
我们分析一下。gcd 算法的停止条件应当是余数为0。而在计算的过程中，我们一般需要三个变量的空间，用于存放 p、q 和它们的计算结果 r，如果计算仍需进行，我们需要将 q 的值移动至 p，r 的值移动至 q，这样就维护了p % q计算循环的正确性：
int gcd(int p, int q) {
int r = q;
while (r != 0) {
r = p % q;
p = q;
q = r;
}
return p;
}
减少一个变量
上面的算法是不是可以减少一个变量的使用呢？
如果我们不使用一个新变量 r 来存放p%q的计算结果，那么这个结果必须放在 p 或 q 所在的内存中。在上面的实现中，我们最终是要用 q 将 p 的值覆盖掉的，说明 p 的值在计算后变得不重要了，我们直接用计算结果覆盖：p = p % q
那么，计算结果 r 现在放在p这个变量上，它需要和q交换一下位置。通用的交换算法需要用到三个变量，似乎我们依然无法避免多声明一个变量？未必，因为 gcd 算法使用的是整型变量，我们可以使用一种只有整型变量能使用的特殊技巧来交换二者的值。
利用XOR交换两个整型变量
按位进行 XOR（异或运算）的规则很简单，若两个操作数相应的位不同则值为1，相同则值为0，比如 15 XOR 19：
00001111
XOR
00010011
=
00011100
异或运算的本质是求出两个操作数在每一个位上的 diff 信息
由于位只有两种状态，因此，一个操作数结合 diff 信息，得到另一个操作数是轻而易举的事情——只需要再进行一次异或。用简单的等式（注意不是赋值语句）来表示，即b=a^b^a。
用扩展的角度来看，a、b、a^b 之间形成一种三角关系：a^b 代表 a 与 b 的 diff 信息，而 b 代表了 a 和 a^b 的 diff 信息，a 代表了 b 和 a^b 的 diff 信息。
因而，只要我们知道这个三角关系的任意两个值，都可以计算得出第三个值。（异或的逆运算是自身）
有两种角度理解 XOR：
其一是从生成两个操作数的 diff 信息这个角度来理解，即，不同为1，相同为0
其二是操作数根据 diff 信息还原出另一个操作数的角度来理解。我们把 diff 的每一个位理解成：若 diff 的某一位是0，说明希望保持这个位；若 diff 的某一位是 1，说明希望翻转这个位。
根据异或运算的特点，我们可以做到只使用两个变量来交换两个整型：
void swap(int &a, int &b) {
a = a^b;
b = a^b; // 相当于a^b^b
a = a^b; // 相当于a^b^a
}
二元运算与整型变量交换
如何理解上面的代码呢？我们换个更简单的二元运算——加法，来进一步说明这个问题。使用加法来交换两个整型更加直观且直接（我们不这么做的理由是加法可能会导致结果溢出，因此显得不如异或可靠）
void swap(int &a, int &b) {
a = a + b; // 先计算一个同时包含a和b的结果
b = a - b; // 通过b进行逆运算, 求原来的a
a = a - b; // 通过原来的a进行逆运算，求原来的b
}
仔细对比使用异或运算或加减法运算对整型变量进行交换的步骤，我们可以更清楚地知道二元运算是怎么产生作用的。
首先，我们用可逆的二元运算，计算出一个同时包含操作数 a 和 b 的结果，然后使用逆运算还原想要的另一个操作数即可达成变量交换的效果。对于异或运算来说，它的逆运算就是其自身。
另一个版本的gcd
我们知道如何使用二元运算交换整型变量后，照葫芦画瓢修改原来的 gcd 算法即可：
int gcd_no(int p, int q) {
while (q != 0) {
p = p % q;
p = p^q;
q = p^q;
p = p^q;
}
return p;
}
这个算法会更高效吗？答案是未必，它虽然减少了一个栈变量的使用，但是却可能增加了一次内存访问。