位运算数组操作

Question

给定一个包含N个正整数（1 <= A[i] <= 10^9）的数组A。

令F(i,j,k)=(A[i] | A[j]) & A[k]， 其中 | 表示按位或，&表示按位与。 任务是确定对于所有满足1 <= A,B,C <= N的三元组(A,B,C)，F(A,B,C)的按位异或。

例如: 如果N=2且A=[1,4] 三元组将会是:

F(1,1,1) = 1 F(1,1,2) = 0 F(1,2,1) = 1 F(1,2,2) = 4 F(2,1,1) = 1 F(2,1,2) = 4 F(2,2,1) = 0 F(2,2,2) = 4 所有的按位异或结果为：1^0^1^4^1^4^0^4 = 5 因此答案是5。

又如： 如果A=[14,9,19,18,17,11,12]，那么答案是16。

如何解决这个问题或如何处理这种问题？ JavaScript代码可能有所帮助，但其他语言也可以。

- Yash Bhardwaj

---

你在寻找什么？比暴力破解更好的方法吗？否则，只需对于问题中定义的所有三元组(x, y, z)，使用异或运算f(x, y, z)即可。 - user1984

Answer 1

这种问题可以通过逐个考虑每个比特位来解决。

对于每个比特位，让n0是该比特位为0的数组元素数，n1是该比特位为1的元素数。

然后很容易确定答案中是否设置了该位：

- 在A[i] | A[j]中设置位的对数i，j是n1 * n1 + n1 * n0 * 2。 - 然后在F（i，j，k）中设置该位的三元组i，j，k的数量为n1 *（n1 * n1 + n1 * n0 * 2）。 - 由于所有F都异或在一起，如果三元组的奇数个数设置了该位，则结果将设置该位，即如果上述表达式计算为奇数，则设置该位。

此时，我们可以通过计算每个比特位的1和0来轻松解决问题，但请注意，当n1为奇数时，即当该位在数组中出现奇数次时，n1 *（n1 * n1 + n1 * n0 * 2）会计算为奇数。为了得到一个数字，如果它在数组中出现奇数次则设置每个位...

只需将所有数组元素进行异或操作。

- Matt Timmermans

Answer 2

@Matt提供的第一个解决方案相当不错。以下是另一种使用简单数学技巧的解决方案。

在下面，我将使用XOR的求和符号，并使用“&”的乘积符号。

问题是计算F = sum F(i, j, k) = sum_{i, j, k} (A[i]|A[j]).A[k]。

通过使用乘法（&）在加法（xor）上的分配律，我们得到：

F = sum_k A[k] . sum_{i, j} (A[i] | A[j])

我们注意到，

A[i] | A[j] = A[i] + A[j] + A[i].A[j]

那么

sum_{i, j} (A[i] | A[j]) = sum_{i, j} (A[i] + A[j] + A[i].A[j])

由于 A + A = 0，因此显然有 sum_{i, j} (A[i] + A[j] = 0

此外，if (i != j), A[i].A[j] + A[j].A[i] = 0。因此，

sum_{i, j} A[i].A[j] = sum_i A[i].A[i] = sum_i A[i]

我们在这里使用了 A & A = A。

最后，

F = sum_k A[k] . sum_k A[k] = sum_k A[k]

解决方法是取数组中所有元素的异或值。

- Damien

---

你能解释一下第三步吗？你是如何将AND分配到XOR上的？另外，我不太理解你的符号sum_{i,j,k}，能否再详细解释一下它的含义？ - NoSuchUserException

Sum_{I,j,k} micmic 数学 LaTeX 符号。i 从 1 到 N，j 从 1 到 N，k 从 1 到 N 进行求和。对于分配律：逻辑 AND 对应于集合 {0, 1} 中的乘法，即 Galois 域 GF(2)，而 xor 对应于同一域中的加法。 (A and B) xor (A and C) = A and (B xor C)。@NoSuchUserException。 - Damien

所以你刚才是反过来使用了分配律，也就是将 (A&B) xor (A&C) 写成了 A & (B xor C)？另外，latex 符号表示对于所有的 i、j、k（从 1 到 N），都进行异或运算。我仍然无法想象你如何在不展开 latex 表达式的情况下使用分配律，这可能与布尔代数中的某些规则有关。@Damien - NoSuchUserException

在GF(2)中，将异或视为加法，将与视为乘法。 - Damien