Thank you very much for reading this article~
Welcome[ 👍 [like][ ⭐ Collection][ 📝 [comments]~
It's not hard to give up, but it must be cool to insist~
I hope all of us can make a little progress every day~
This paper consists of The white hat of the second leader https://le-yi.blog.csdn.net/ Blog originality~

1486. Array XOR operation:

I'll give you two integers, n and start.

The array num is defined as: num [i] = start + 2 * I (subscript starts from 0) and N = = num.length.

Please return the result obtained after bitwise XOR (XOR) of all elements in nums.

Example 1

Input:
	n = 5, start = 0
 Output:
	8
 Explanation:
	array nums by [0, 2, 4, 6, 8]，among (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 . 
     "^" Bitwise XOR XOR Operator.

Example 2

Input:
	n = 4, start = 3
 Output:
	8
 Explanation:
	array nums by [3, 5, 7, 9]，among (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3

Input:
	n = 1, start = 7
 Output:
	7

Example 4

Input:
	n = 10, start = 5
 Output:
	2

Tips

• 1 <= n <= 1000
• 0 <= start <= 1000
• n == nums.length

analysis

We can directly follow the meaning of the question, violence cycle, so the time complexity is O(n). Is there an algorithm with time complexity of O(1)?

If x is a variable and ^ is an XOR operation, the XOR operation satisfies the following properties:

1. x ^ x = 0；
2. x ^ 0 = x；
3. x ^ y = y ^ x (commutative law);
4. (x ^ y) ^ z = x ^ (y ^ z) (associative law);
5. x ^ y ^ y = x (reflexivity);
6. If x is a multiple of 4, x ^ (x + 1) ^ (x + 2) ^ (x + 3) = 0;

• The result formula to be calculated is: start ^ (start + 2) ^ (start + 4) ^... ^ (start + 2 * (n − 1)).
• If there is a function sumXor(x), it can calculate 0 ^ 1 ^ 2 ^... X.
• For some variables x and N, calculate the result of sumXor(s - 1) ^ sumXor(s + n - 1). According to the above property 1, the value of 0 ^ 1 ^ 2 ^... ^ (s - 1) can be offset to 0, and it becomes 0 ^ s ^ (s + 1) ^ (s + 2) ^... ^ (s + n - 1). According to the property 2, it can be known whether the operation is different from 0 or self, and the final result becomes s ^ (s + 1) ^ (s + 2) ^... ^ (s + n - 1), This result is very close to what we want to calculate.
• If we make s = start / 2 and convert the result formula to (s ^ (s + 1) ^ (s + 2) ^... ^ (s + n - 1)) * 2, this does not hold because the lowest bit is lost when dividing by 2, but we can deal with the lowest bit separately.
• The observation result formula shows that the parity properties of (start + 2), (start + 4),..., (start + 2 * (n − 1)) are the same and consistent with start, that is, the lowest bit is either 0 or 1. It will be 1 only when the cardinal 1 performs XOR operation. That is, only when start is odd and N is odd, the lowest e of the final result will be 1.
• At this time, the result formula can be transformed into: (sumXor(s - 1) ^ sumXor((s + n - 1)) | e.

As long as we can implement the function sumXor(x), the problem calculation can achieve the time complexity of O(1). According to property 6 and property 2, we only need to consider the remainder of X divided by 4, that is, the lowest 2 bits, and the following derivation can be obtained:

Binary bits of X% 4 = 0: xx... x00
Binary bits of X% 4 = 1: xx... x01
Binary bits of X% 4 = 2: xx... x10
Binary bits of X% 4 = 3: xx... x11

• x % 4 = 0，sumXor(x) = x；
• X% 4 = 1, sumXor(x) = (x - 1) ^ x, sumXor(x) = 1;
• X% 4 = 2, sumXor(x) = (x - 2) ^ (x - 1) ^ x, simplified sumXor(x) = x | 1;
• x % 4 = 3，sumXor(x) = 0；
• X% 4 is equivalent to the operation of X & 3, and theoretically & operation is faster than% operation;

Problem solution

java

class Solution {
    public int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    public int sumXor(int x) {
        switch (x & 3) {
            case 0:
                return x;
            case 1:
                return 1;
            case 2:
                return x | 1;
            default:
                // x & 3 == 3
                return 0;
        }
    }
}

c

int xorOperation(int n, int start) {
    int s = start >> 1, e = n & start & 1;
    int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
    return ret << 1 | e;
}

int sumXor(int x) {
    switch (x & 3) {
        case 0:
            return x;
        case 1:
            return 1;
        case 2:
            return x | 1;
        default:
            // x & 3 == 3
            return 0;
    }
}

c++

class Solution {
public:
    int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    int sumXor(int x) {
        switch (x & 3) {
            case 0:
                return x;
            case 1:
                return 1;
            case 2:
                return x | 1;
            default:
                // x & 3 == 3
                return 0;
        }
    }
};

python

class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        def sumXor(x):
            if x % 4 == 0:
                return x
            if x % 4 == 1:
                return 1
            if x % 4 == 2:
                return x | 1
            return 0
        s = start >> 1
        e = n & start & 1
        ans = sumXor(s - 1) ^ sumXor(s + n - 1)
        return ans << 1 | e

go

func xorOperation(n, start int) (ans int) {
    s, e := start>>1, n&start&1
    ret := sumXor(s-1) ^ sumXor(s+n-1)
    return ret<<1 | e
}

func sumXor(x int) int {
    switch x & 3 {
        case 0:
            return x
        case 1:
            return 1
        case 2:
            return x | 1
        default:
            return 0
    }
}

rust

impl Solution { 
  pub fn xor_operation(n: i32, start: i32) -> i32 {
    let s = start >> 1;
    let e = n & start & 1;
    let ret = Solution::sum_xor(s - 1) ^ Solution::sum_xor(s + n - 1);
    return ret << 1 | e
  }

  fn sum_xor(x: i32) -> i32 {
    match x & 3 {
      0 => x,
      1 => 1,
      2 => x | 1,
      _ => 0
    }
  }
}

Original title portal