1

以下は、「その場で」文字列を逆にする、つまり Black Cat が Cat Black になるメソッドです。2 番目のスワップ セクションでは、従来のスワップ (コメント アウト) を使用するとすべてのテストに合格しますが、XOR スワップを使用すると 1 つのテストしか合格しません。

単に「交換」することはできませんか

        for (int i = count; i <= (end + count) / 2; i++) {
            char temp = arr[i];
            arr[i] = arr[end - (i - count)];
            arr[end - (i - count)] = temp;
        }

に

        for (int i = count; i <= (end + count) / 2; i++) {
            arr[i] ^= arr[end - (i - count)];
            arr[end - (i - count)] ^= arr[i];
            arr[i] ^= arr[end - (i - count)];
        }

方法

public class ReverseString {

    public static char[] revString(String input) {

        char[] arr = input.toCharArray();
        int length = arr.length;

        for (int i = 0; i < (length / 2); i++) {
            arr[i] ^= arr[length - i - 1];
            arr[length - i - 1] ^= arr[i];
            arr[i] ^= arr[length - i - 1];  
        }

        int end;
        int charCount;
        int count = 0;
        while (count < length) {

            if (arr[count] != ' ') {

                charCount = 0;              
                while (count + charCount < length && arr[count + charCount] != ' ') {
                    charCount++;
                }

                end = count + charCount - 1;

//              for (int i = count; i <= (end + count) / 2; i++) {
//                  char temp = arr[i];
//                  arr[i] = arr[end - (i - count)];
//                  arr[end - (i - count)] = temp;
//              }

                for (int i = count; i <= (end + count) / 2; i++) {
                    arr[i] ^= arr[end - (i - count)];
                    arr[end - (i - count)] ^= arr[i];
                    arr[i] ^= arr[end - (i - count)];
                }

                count += charCount;

            } else {
                count++;
            }           
        }
        return arr;
    }   
}

テスト

@RunWith(JUnitParamsRunner.class)
public class ReverseStringTest {

    @Test
    @Parameters(method = "getStrings")
    public void testRevString(String testValue, char[] expectedValue) {     
        assertThat(ReverseString.revString(testValue), equalTo(expectedValue));     
    }

    private static final Object[] getStrings() {
        return new Object[] {
            new Object[] {"Black Cat", "Cat Black".toCharArray()},
            new Object[] {"left to", "to left".toCharArray()}
        };
    }   
}

失敗時の出力

java.lang.AssertionError: 
Expected: ["C", "a", "t", " ", "B", "l", "a", "c", "k"]
but: was ["C", "
4

1 に答える 1

2

値をそれ自体と交換すると、XOR スワップが失敗します。コードは次のとおりです。

arr[i] ^= arr[end - (i - count)];
arr[end - (i - count)] ^= arr[i];
arr[i] ^= arr[end - (i - count)];

と仮定しましょうi == end - (i - count)。それで：

arr[i] ^= arr[end - (i - count)];

ゼロに設定arr[i]します (それ自体で XOR されたものはすべてゼロであるため)。

次の 2 行は何もしません。ゼロを使用した XOR は効果がなく、arr[i]ゼロのままで入力が破損するためです。

あなたが指摘したように、上記の仮定が真であるかどうかは、入力の長さに依存します。

この問題があるため、XOR スワッピングは危険です。また、読みにくく、最新のプラットフォームではパフォーマンスが向上しないため、このマイクロ最適化のトリックは時代遅れであり、避ける必要があります。

于 2015-03-09T22:54:33.207 に答える