我们有一个数组A (say [1,2,3])。我们需要找到数组中所有整数对的 XOR（^）SUM 。尽管可以轻松完成此操作，O(n^2)但是如何提高解决方案的复杂性？例如，上面的数组A，答案是“ (1^2)+(1^3)+(2^3) = 6 谢谢”。
A (say [1,2,3])
O(n^2)
(1^2)+(1^3)+(2^3) = 6
您可以分开计算一次只做一位。
例如，查看数组中所有数字的最右边。假设a数字具有最右边的0位，b数字具有1位。然后，在这些对中，a*b它们在XOR的最右位将为1。这是因为有a*b多种方法可以选择一个具有0位的数字和具有1位的数字。因此，这些位a*b将占所有XOR的总和。
a
b
a*b
通常，查看n第th位（最右边的位是0）时，请计算有0的数字（称为a n）和有1的数字（称为b n）。对最终和的贡献将是n * b n * 2 n。您需要对每个位进行此操作，并将所有这些贡献加在一起。
n
可以在O（kn）时间中完成，其中O k是给定值中的位数。
k
