跳至主要內容

1486. 数组异或操作

ITCharge大约 2 分钟

1486. 数组异或操作open in new window

  • 标签:位运算、数学
  • 难度:简单

题目链接

题目大意

给定两个整数 n、start。数组 nums 定义为:nums[i] = start + 2*i(下标从 0 开始)。n 为数组长度。返回数组 nums 中所有元素按位异或(XOR)后得到的结果。

解题思路

1. 模拟

直接按照题目要求模拟即可。

2. 规律

  • xx=0x \oplus x = 0
  • xy=yxx \oplus y = y \oplus x(交换律);
  • (xy)z=x(yz)(x \oplus y) \oplus z = x \oplus (y \oplus z)(结合律);
  • xyy=xx \oplus y \oplus y = x(自反性);
  • iZ\forall i \in Z,有 4i(4i+1)(4i+2)(4i+3)=04i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0
  • iZ\forall i \in Z,有 2i(2i+1)=12i \oplus (2i+1) = 1
  • iZ\forall i \in Z,有 2i1=2i+12i \oplus 1 = 2i+1

本题中计算的是 start(start+2)(start+4)(start+6)(start+(2(n1)))start \oplus (start + 2) \oplus (start + 4) \oplus (start + 6) \oplus … \oplus (start+(2*(n-1)))

可以看出,若 start 为奇数,则 start+2,start+4,,start+(2×(n1))start+2, start + 4, …, start + (2 \times(n - 1)) 都为奇数。若 start 为偶数,则 start+2,start+4,,start+(2×(n1))start + 2, start + 4, …, start + (2 \times(n - 1)) 都为偶数。则它们对应二进制的最低位相同,则我们可以将最低位提取处理单独处理。从而将公式转换一下。

s=start2s = \frac{start}{2},则等式变为 (s)(s+1)(s+2)(s+3)(s+(n1))2+e(s) \oplus (s+1) \oplus (s+2) \oplus (s+3) \oplus … \oplus (s+(n-1)) * 2 + e,e 表示运算结果的最低位。

根据自反性,(s)(s+1)(s+2)(s+3)(s+(n1))=(12(s1))(12(s1)(s)(s+1)(s+(n1)))(s) \oplus (s+1) \oplus (s+2) \oplus (s+3) \oplus … \oplus (s+(n-1)) = \\ (1 \oplus 2 \oplus … \oplus (s-1)) \oplus (1 \oplus 2 \oplus … \oplus (s-1) \oplus (s) \oplus (s+1) \oplus … \oplus (s+(n-1)))

例如: 34567=(12)(1234567)3 \oplus 4 \oplus 5 \oplus 6 \oplus 7 = (1 \oplus 2) \oplus (1 \oplus 2 \oplus 3 \oplus 4 \oplus 5 \oplus 6 \oplus7)

就变为了计算前 n 项序列的异或值。假设我们定义一个函数 sumXor(x) 用于计算前 n 项数的异或结果,通过观察可得出:

sumXor(x) = \begin{cases} \begin{array} \ x, & x = 4i, k \in Z \cr (x-1) \oplus x, & x = 4i+1, k \in Z \cr (x-2) \oplus (x-1) \oplus x, & x = 4i+2, k \in Z \cr (x-3) \oplus (x-2) \oplus (x-3) \oplus x, & x = 4i+3, k \in Z \end{array} \end{cases}

继续化简得:

sumXor(x) = \begin{cases} \begin{array} \ x, & x = 4i, k \in Z \cr 1, & x = 4i+1, k \in Z \cr x+1, & x = 4i+2, k \in Z \cr 0, & x = 4i+3, k \in Z \end{array} \end{cases}

则最终结果为 sumXor(s1)sumXor(s+n1)2+esumXor(s-1) \oplus sumXor(s+n-1) * 2 + e

下面还有最后一位 e 的计算。

  • 若 start 为偶数,则最后一位 e 为 0。
  • 若 start 为奇数,最后一位 e 跟 n 有关,若 n 为奇数,则最后一位 e 为 1,若 n 为偶数,则最后一位 e 为 0。

总结下来就是 e = start & n & 1

代码

  1. 模拟
class Solution:
    def xorOperation(self, n: int, start: int) -> int:
        ans = 0
        for i in range(n):
            ans ^= (start + i * 2)
        return ans
  1. 规律
class Solution:
    def sumXor(self, x):
        if x % 4 == 0:
            return x
        if x % 4 == 1:
            return 1
        if x % 4 == 2:
            return x + 1
        return 0
    def xorOperation(self, n: int, start: int) -> int:
        s = start >> 1
        e = n & start & 1
        ans = self.sumXor(s-1) ^ self.sumXor(s + n - 1)
        return ans << 1 | e