重复对连续元素进行异或
Repetitively taking XOR of consecutive elements
给定一个大小为 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)
时间。有没有更高效的解决问题的方法?
这个问题有一个非常有效的解决方案,只需要几行代码,但解释起来相当复杂。无论如何,我会去的。
假设您需要减少一个列表,比方说,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 中)。
给定一个大小为 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)
时间。有没有更高效的解决问题的方法?
这个问题有一个非常有效的解决方案,只需要几行代码,但解释起来相当复杂。无论如何,我会去的。
假设您需要减少一个列表,比方说,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 中)。