8

这是原始代码：

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--] ？

4

5 回答 5

14

代码相当于

    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位都被交换了。当语句应用于更大的整数时，^运算符并行处理所有位，因此最终结果是每对位都被交换，即整个值都被交换。

于 2016-10-27T04:04:27.500 回答
2

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

现在以这个为例说A^B，ith第1位，这意味着第i位A和B不同。意思是其中一个是1，另一个是0。

现在当我们这样做时(A^B)^B，如果第 i 个位 inB是0，我们将得到1since 1^0 = 1，它等于ithbit inA和(A^B)^A = 0，即ithbit in B。

类似地，当第 i 位为 B is1且 in Ais0时，再次发生交换。

ith当bit in A^Bis时，同样的逻辑也适用0。你可以很容易地验证它。

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

于 2016-10-27T04:08:41.570 回答
0

首先考虑交换两个数值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 执行交换相当于对每个位模 2 执行上述“加法交换”。但是，表达式可以简化，因为除了模 2，每个数字都是它自己的倒数（等效地，加法和减法是相同）。这（具有交换性）给了我们熟悉的：

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

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

于 2016-11-01T03:31:16.867 回答
0

如果你同意这一点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。

于 2016-10-30T16:19:08.077 回答
0

下面的例程预计将交换和的a值b

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

让我们分析一下交换是如何以及为什么起作用的。

为此，我们不要交换值，而是将它们存储在单独的变量中，这样我们就可以看到到底发生了什么。

a0 = a ^ b
b1 = b ^ a0
a1 = a0 ^ b1

使用 XOR 的以下属性简化方程。检查XOR Properties@Wikipedia以供参考

  1. 可交换的 ( a ^ b == b ^ a)
  2. 联想 ( a ^ (b ^ c) == (a ^ b) ^ c)
  3. a ^ a == 0
  4. 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

如您所见，b1now 包含 的原始值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

想象 的新值是生成given的旧值或生成givena的旧值的掩码。abba

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

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

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

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

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

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

于 2016-10-30T11:12:49.833 回答