按位数组操作

Question

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

设 F(i,j,k) = ( A[i] | A[j] ) & A[k]
| 表示按位 OR，& 表示按位 AND
任务是确定 F(A,B,C) 对所有三元组 (A,B,C) 的按位异或，使得 1<= A,B,C <=N

例如：
如果 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 代码会很有帮助，但也欢迎其他语言。

Answer 1

这类问题可以通过单独考虑每一位来解决。

对于每个位，令 n0 为该位设置为 0 的数组元素的数量，并令 n1 为该位设置为 1 的元素的数量。

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

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

此时，我们可以通过计算每个位的 1 和 0 来轻松解决问题，但请注意，当为奇数时，即当该位在数组中出现奇数次时，n1*(n1*n1 + n1*n0*2)计算结果恰好为奇数。n1如果在数组中设置了奇数次，则要获取每个位设置的数字...

只需将所有数组元素异或在一起即可。