以下程序旨在交换变量
a
和
b
的值。
a = a ^ b
b = b ^ a
a = a ^ b
让我们分析一下交换操作的原理和过程。
为此,我们不直接交换变量的值,而是将它们存储在不同的变量中,这样我们就可以清楚地看到具体的操作过程。
a0 = a ^ b
b1 = b ^ a0
a1 = a0 ^ b1
使用 XOR 下面的性质简化方程。请参考XOR Properties@Wikipedia。
- 交换律 (
a ^ b == b ^ a
)
- 结合律 (
a ^ (b ^ c) == (a ^ b) ^ c
)
a ^ a == 0
0 ^ a == a
a0 = a ^ b // Equation #1
b1 = b ^ a0
a1 = a0 ^ b1
b1 = b ^ a0 // Equation #2
= b ^ (a ^ b) // Using Equation #1
= b ^ (b ^ a) // Property #1
= (b ^ b) ^ a // Property #2
= 0 ^ a // Property #3
= a // Property #4
a1 = a0 ^ b1
= a0 ^ (b ^ a0) // Using Equation #2
= (a ^ b) ^ (b ^ (a ^ b)) // Using Equation #1
= (b ^ a) ^ (b ^ (b ^ a)) // Using Property #1
= (b ^ a) ^ ((b ^ b) ^ a) // Using Property #2
= (b ^ a) ^ (0 ^ a) // Using Property #3
= (b ^ a) ^ a // Using Property #4
= b ^ (a ^ a) // Using Property #2
= b ^ 0 // Using Property #3
= b // Using Property #4
如您所见,b1
现在包含了 a
的原始值,而 a1
包含了 b
的原始值,即 b
和 a
的值被交换了。
总之,a^=b;b^=a;a^=b
只是一种惯用表达,其中并没有什么神奇的地方 :)
相同内容的普通英语解释
XOR 在操作数位不同时设置位,并在操作数位相同时重置位。
让我们通过一个例子来演示发生的转换。为此,假设我们将以下数字(以二进制形式)分配给变量。
a = 1 1 0 0
b = 1 0 1 0
步骤 #1: a = a ^ b
// 创建掩码
a = 0 1 1 0
b = 1 0 1 0
假设a
的新值是用于生成给定b
的旧值或生成给定a
的旧值的掩码。
步骤#2:b = b ^ a
//使用掩码和b
的原始值恢复a
的原始值
a = 0 1 1 0
b = 1 1 0 0
由于b
仍然被保留/未更改,我们可以使用掩码恢复a
的原始值 - 这就是我们在此步骤中所做的。
第三步: a = a ^ b
// 使用掩码和a
的原始值恢复b
的原始值
a = 1 0 1 0
b = 1 1 0 0
现在我们在变量
b
中有了变量
a
的原始值,因此我们可以使用相同的掩码来恢复变量
b
的原始值。由于在这一步之后我们不再需要掩码,因此我们现在可以覆盖掉它。
rev[i++]^=rev[j--]
same with:rev[i]^=rev[j];i++;j++;
it swaps one more time then incrementi
andj
- malioboro