形式 (start + 2 * i) 的所有元素的异或，其中 i 的范围从 0 到 n - 1

Question

背景：

这道题实际上在leetcode上被归类为一个简单的问题，其解决方案的时间复杂度为O(N)。

但我很难理解其他用户使用位操作和一些观察得出的时间复杂度为 O(1) 的解决方案。

问题陈述：

给定一个整数 n 和一个整数 start。

定义数组 nums，其中 nums[i] = start + 2*i（0 索引）和 n == nums.length。

Return nums 的所有元素的按位异或。

O(1)用户解法：

class Solution {
public:
    int xorOperation(int n, int start) {
        int first = start & 1;
        start = start >> 1;
        if(start % 2 == 0){
            switch(n % 4){
                case 0: return 0;
                case 1: return ((start + n - 1) << 1) + first;
                case 2: return 2;
                case 3: return ((1 ^ (start + n - 1)) << 1) + first;
            } 
        } else {
            switch(n % 4){
                case 0: return (start ^ 1 ^ (start + n - 1)) << 1;
                case 1: return (start << 1) + first;
                case 2: return (start ^ (start + n - 1)) << 1;
                case 3: return ((start ^ 1) << 1) + first;
            } 
        }
        return 0; //unreachable
    }
};

他说当 x 是偶数时，他使用了 x ^ (x + 1) = 1 的观察结果，但我不明白这个信息有什么用。

一些我可能不知道的关于概念的信息将非常有用。

Answer 1

不确定为什么您发布的代码如此复杂，但我认为我找到了一个更易于解释（并且更易于启动）的解决方案

首先，让我们做一些观察

你总是添加一个 2 * 数字，所以 start 的最低位只是与它自己异或 n 次，这与如果它与 n&1 相加（如果 n 是奇数，它保持原样，如果它是偶数，它总是 0 ）。所以，让我们单独计算它并将其分流到输出并处理其余部分
```
int firstBit = start & n & 1;
int startHi = start >> 1;
// the formula now being just num[i]=startHi+i
// ... here be computation ...
//
return firstBit | ( resultHi << 1 );
```
xor 是结合的并且它自己是逆的，所以

A^B^C^D^E^F^G^H = (A^B^C^D)^(E^F^G^H)

(E^F^G^H) = (A^B^C^D)^(A^B^C^D^E^F^G^H)

所以我们可以根据 xor(0...m) 求解 xor(m...n) 和xor(0...n) 或者，根据 start 和 n，我们可以

(start+0^start+1^...start+n-1) = (0^1^2^....start-1) ^ (0^1^2^....start+n-1)

让我们定义一个更简单的 1 参数函数 xor0(k)，结果将是
```
    int firstBit = start & n & 1;
    int startHi = start >> 1;
    int resultHi = xor0(startHi)^xor0(startHi+n);
    return firstBit | ( resultHi << 1 );
```
如果我们对数字 0...k-1 进行异或运算，看看这些位是什么样的
- 第一位像 0101 0101 0101 0101 0101,
  
  所以异或值就像 0110 0110 0110 0110 我们可以立即看到模式并计算
  
  int firstBit = (k&2)>>1;
- 对于所有其他位，以位2为例，
  
  它会 0000 1111 0000 1111
  
  所以异或值是 0000 1010 0000 1010
  
  或位 3 0000 0000 1111 1111 0000 0000 1111 1111
  
  异或后的值是 0000 0000 1010 1010 0000 0000 1010 1010，
我们也可以立即看到模式：如果该位为 0，则它保持为 0，如果该位为 1，则输出在奇数 k 的 1 和奇数的 0 之间交替甚至 k，所以我们可以 int higherBits= (k-1) & ( (k&1)==0 ? 0 : -2 );

因此我们有了最终版本（在 java 中，通过自检将其与参考 O(N) 实现进行比较）

package xortest;

public class XorTest {

    public static void main (String[] args) {
        for (int s = 0; s < 16; s++) {
            for (int n = 0; n < 16; n++) {
                int r = xorReference(s, n);
                int x = xorOperation(s, n);
                System.out.println(String.format("s=%02d n=%02d ref=%08x val=%08x%s", s, n, r, x, x == r ? "" : " ERROR"));
            }
        }
    }

    static int xor0(int k) {
        int firstBit = (k & 2) >> 1;
        int higherBits = (k - 1) & ((k & 1) == 0 ? 0 : -2);
        return higherBits | firstBit;
    }

    static int xorOperation(int start, int n) {
        int firstBit = start & n & 1;
        int startHi = start >> 1;
        int resultHi = xor0(startHi) ^ xor0(startHi + n);
        return firstBit | (resultHi << 1);
    }

    static int xorReference(int start, int n) {
        int xor = 0;
        for (int i = 0; i < n; i++) {
            xor ^= start + 2 * i;
        }
        return xor;
    }
    
}

形式 (start + 2 * i) 的所有元素的异或，其中 i 的范围从 0 到 n - 1

XOR of all the elements of form (start + 2 * i) where i ranges from 0 to n - 1

bit-manipulation

bit

bit-shift

xor

bitwise-xor