1

下面是一种执行“就地”字符串反转的方法，即 Black Cat 变为 Cat Black。在第二个交换部分，如果使用传统交换（已注释掉），则所有测试都通过，但是如果使用 XOR 交换，则只有一个测试通过。

难道不能简单地“交换”

        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]为零（因为任何与自身异或的东西都是零）。

接下来的两行什么都不做，因为与零进行异或运算没有效果，保留arr[i]为零，从而破坏了您的输入。

正如您所指出的，上述假设是否正确取决于输入的长度。

由于这个问题，异或交换是危险的。由于它也很难阅读，并且在任何现代平台上都不会带来性能优势，因此这种微优化技巧已经过时，应该避免使用。

于 2015-03-09T22:54:33.207 回答