Xor 如何交换值？

Question

原代码如下：

public static String reverseString(String s){       
    if(s == null) return "";        
    char[] rev = s.toCharArray();
    int i = 0, j = s.length() - 1;
    while(i < j) {
        rev[i] ^= rev[j];
        rev[j] ^= rev[i];
        rev[i++] ^= rev[j--];           
    }       
    return String.valueOf(rev); 
}

我的问题是 Xor 如何在这里交换字符值，为什么这里需要 rev[i++]^=rev[j--]？

Answer 1

代码等同于

    rev[i] ^= rev[j];
    rev[j] ^= rev[i];
    rev[i] ^= rev[j];           
    i++;  j--;

最后一部分只需要为下一次循环迭代递增 i 和递减 j。

至于为什么x ^= y; y ^= x; x ^= y可以交换值，我不知道为什么，但是你可以看到它适用于1位值在所有四种可能性中：

 start   after x^=y  after y^=x   after x^=y
x    y     x   y       x   y        x   y
0    0     0   0       0   0        0   0
0    1     1   1       1   0        1   0
1    0     1   0       1   1        0   1
1    1     0   1       0   1        1   1

所以你可以看到在所有情况下，x 和 y 位都被交换了。当语句应用于更大的整数时，^ 运算符并行处理所有位，因此最终结果是交换每一对位，即交换整个值。

Answer 2

XOR 运算符 有一个非常独特的运算符，它充当 不等式检测器 意味着只有当两个位不同时结果才会 1 否则结果是 0.

现在拿这个举例来说在A^B, ith bit 1, 这意味着A和B的第i位不同。意思是其中一个是 1 而另一个是 0.

现在当我们这样做 (A^B)^B 时，如果 B 中的第 i 位是 0，我们将得到 1，因为 1^0 = 1，等于 A 中的 ith 位和 (A^B)^A = 0 中的 ith 位，即 B.

中的 ith 位

同理，当第i位B为1而A为0时，再次发生交换。

当 A^B 中的 ith 位为 0 时，同样的逻辑适用。你可以很容易地验证它。

很容易看出交换是如何发生的，当您将原始数字与 A^B 异或时，您会得到另一个数字，因为 交换发生在每个位

Answer 3

下面的例程应该交换 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只是一个地道的表达，没有什么神奇之处:)

同样的简单英语解释

当操作数位不同时异或设置位，否则重置位

让我们通过示例来了解发生的转换。为此，我们将以下数字（二进制）分配给变量。

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 的旧值或在给定 [=17] 的情况下生成 b 的旧值=].

步骤 #2: b = b ^ a // 使用掩码和 b[=48= 的原始值恢复 a 的原始值]

a = 0 1 1 0
b = 1 1 0 0

由于 b 仍然是 preserved/untouched，我们可以使用掩码恢复 a 的原始值 - 这就是我们在这一步中所做的

步骤 #3: a = a ^ b // 使用掩码和原始值恢复 b 的原始值共 a

a = 1 0 1 0
b = 1 1 0 0

现在我们在变量b中有了a的原始值，所以我们可以使用相同的掩码来恢复b的原始值。我们现在可以覆盖掩码，因为在这一步之后我们不需要掩码。

Answer 4

如果您同意y == (x^y)^x == x^(y^x)，那么您就有答案了。

考虑您提供的代码中循环体的抽象版本：

a = a ^ b
b = b ^ a
a = a ^ b

现在重命名一个值以阐明发生了什么：

a_xor_b = a ^ b
b = b ^ a_xor_b // Now b is the original a because b^(a^b) == a!
a = a_xor_b ^ b // Now a is the original b because (a^b)^a == b!

现在请注意，如果 a_xor_b 与 a 是同一个变量，则代码可以正常工作。

Answer 5

首先考虑交换两个数值 a 和 b 的不同（但密切相关）的方式可能更容易：

a =  a + b;
b =  a - b;
a = -b + a;

这既适用于纯任意精度的数字，也适用于以 N 为模的整数（当它们变得太大或太小时环绕的整数，就像它们在 Java 中所做的那样）。

为了从数学上分析这一点，我们应该在每次值发生变化时分配一个新符号，这样 = 就可以表示数学上的相等性而不是赋值。那么，这只是基础代数的问题。

a1 = a0 + b0
b2 = a1 - b0 = (a0 + b0) - b0 = a0
a2 = -b2 + a1 = -(a0) + (a0 + b0) = b0

异或呢？解释 XOR 的一种方法是将其视为不带进位的二进制加法。然后用 XOR 执行交换相当于对每个位执行上面描述的 "addition swap" 模 2。表达式可以简化，但是，因为除了模 2，每个数字都是它自己的倒数（等效地，加法和减法是相同的）。这（具有交换性）给了我们熟悉的：

a = a ^ b;
b = b ^ a;
a = a ^ b;

一般来说，上面的 "addition swap" 可以在任何数学 group 中执行（即使它是不可交换的——基本上只需要结合性和逆）。 XOR 的另一种思考方式是它在 n 位整数上引入了一个组结构，因此交换就像在任何组中一样工作。

Xor 如何交换值？

How does Xor work in swapping values?

java

algorithm

bitwise-xor

同样的简单英语解释