重复对连续元素进行异或

Question

给定一个大小为 N

的二进制数组

e.g. A[1:N] = 1 0 0 1 0 1 1 1

将通过取 XOR 个连续的 2 个元素来创建大小为 N-1 的新数组。

A'[1:N-1] = 1 0 1 1 1 0 0

重复此操作，直到剩下一个元素。

1 0 0 1 0 1 1 1
1 0 1 1 1 0 0 
1 1 0 0 1 0
0 1 0 1 1
1 1 1 0
0 0 1
0 1
1

我想找到最后剩下的元素（0 或 1）

重复操作即可找到答案。此方法需要 O(N*N) 时间。有没有更高效的解决问题的方法？

Answer 1

这个问题有一个非常有效的解决方案，只需要几行代码，但解释起来相当复杂。无论如何，我会去的。

假设您需要减少一个列表，比方说，6 个数字除了一个元素外都是零。通过对称性，只需考虑三种情况：

1   0   0   0   0   0      0   1   0   0   0   0      0   0   1   0   0   0
  1   0   0   0   0          1   1   0   0   0          0   1   1   0   0
    1   0   0   0              0   1   0   0              1   0   1   0
      1   0   0                  1   1   0                  1   1   1
        1   0                      0   1                      0   0
          1                          1                          0

在第一种情况下，边缘的单个“1”并没有真正起到任何作用。它基本上只是保持不变。但在另外两种情况下，涉及的列表元素更多，情况更复杂。列表第二个元素中的“1”产生结果“1”，而第三个元素中的“1”产生结果“0”。有没有简单的规则可以解释这种行为？

是的，有。看看这个：

Row 0:             1
Row 1:           1   1
Row 2:         1   2   1
Row 3:       1   3   3   1
Row 4:     1   4   6   4   1
Row 5:   1   5   10  10  5   1

我相信你以前见过这个。它是帕斯卡三角形，其中每一行都是通过添加取自上一行的相邻元素而获得的。三角形中间较大的数字反映了这样一个事实，即这些数字是通过将前面几行的更广泛子集中的值相加而获得的。

注意第5行，中间的两个数都是偶数，而其他数都是奇数。这与上面显示的三个示例的行为完全匹配；偶数个1异或为0，奇数个1异或为1

为了让事情更清楚，我们只考虑这个三角形中数字的奇偶性（即奇数为“1”，偶数为“0”）：

Row 0:             1
Row 1:           1   1
Row 2:         1   0   1
Row 3:       1   1   1   1
Row 4:     1   0   0   0   1
Row 5:   1   1   0   0   1   1

这个其实叫一个Sierpinski triangle。在这个三角形中出现零的地方，它告诉我们你的列表在这个位置是'1'还是'0'并不重要;它对结果值没有影响，因为如果您根据列表中的所有初始值写出显示最终结果值的表达式，则该元素将出现偶数次。

例如，看看第 4 行。除极端边缘外，每个元素均为零。这意味着如果您的列表有 5 个元素，则最终结果仅取决于列表中的第一个和最后一个元素。（这同样适用于任何元素数大于 2 的幂的列表。）

谢尔宾斯基三角形的行很容易计算。如oeis.org/A047999所述：

Lucas's Theorem is that T(n,k) = 1 if and only if the 1's in the binary expansion of k are a subset of the 1's in the binary expansion of n; or equivalently, k AND NOT n is zero, where AND and NOT are bitwise operators.

所以，在冗长的解释之后，这是我的代码：

def xor_reduction(a):
    n, r = len(a), 0
    for k in range(n):
        b = 0 if k & -n > 0 else 1
        r ^= b & a.pop()
    return r

assert xor_reduction([1, 0, 0, 1, 0, 1, 1, 1]) == 1

我说短了。如果你想知道，第 4 行有 k & -n（k AND 减去 n）而不是 k & ~n（k AND not n），因为这个函数中的 n 是列表中元素的数量，它比行号多一，并且 ~(n-1) 与 -n 相同（至少在 Python 中）。

重复对连续元素进行异或

Repetitively taking XOR of consecutive elements

math

xor

bitwise-xor