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はわかりませんが、4 つの可能性すべてを調べると、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 に答える
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

ご覧のとおり、にb1は の元の値が含まれ、 の元の値が含まれています。つまり、との値が入れ替わっています。aa1bba

要約すると、a^=b;b^=a;a^=bは単なる慣用​​表現であり、魔法のようなものは何もありません :)

同じことのわかりやすい英語の説明

XOR は、オペランド ビットが異なる場合にビットを設定し、それ以外の場合はビットをリセットします。

例を使用して、行われる変換を見ていきましょう。そのために、次の数値 (2 進数) が変数に割り当てられているとしましょう。

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

a変数の元の値が得られたbので、同じマスクを使用して の元の値を復元できますb。このステップの後はマスクは必要ないため、ここでマスクを上書きできます。

于 2016-10-30T11:12:49.833 に答える
0

最初に、2 つの数値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 を説明する 1 つの方法は、繰り上げなしの 2 進加算と考えることです。XOR を使用してスワップを実行することは、2 を法とする各ビットに対して上記の「加算スワップ」を実行することと同じです。ただし、2 を法とする加算では、各数値がそれ自体の逆であるため、式は単純化できます (同様に、加算と減算は同じ）。これは (可換性とともに) おなじみのものを与えてくれます:

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

一般に、上記の「加算スワップ」は、任意の数学的グループで実行できます(非可換であっても、基本的には結合性と逆数だけが必要です)。XOR のもう 1 つの考え方は、n ビット整数にグループ構造を誘導するということです。そのため、スワッピングは他のグループと同じように機能します。

于 2016-11-01T03:31:16.867 に答える
0

あなたがそれに同意するならy == (x^y)^x == x^(y^x)、あなたは答えを持っています。

あなたが与えたコードのループ本体の抽象バージョンを考えてみましょう:

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

何が起こっているのかを明確にするために、1 つの値の名前を変更します。

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 に答える