所有对的异或值之和

• Z时代
• 2024-01-10
• 分类：问答

我们有一个数组A (say [1,2,3])。我们需要找到数组中所有整数对的

。尽管可以轻松完成此操作，O(n^2)但是如何提高解决方案的复杂性？例如，上面的数组A，答案是“ (1^2)+(1^3)+(2^3) = 6

谢谢”。

回答：

您可以分开计算一次只做一位。

例如，查看数组中所有数字的最右边。假设a数字具有最右边的0位，b数字具有1位。然后，在这些对中，a*b它们在XOR的最右位将为1。这是因为有a*b多种方法可以选择一个具有0位的数字和具有1位的数字。因此，这些位a*b将占所有XOR的总和。

通常，查看n第th位（最右边的位是0）时，请计算有0的数字（称为a n）和有1的数字（称为b n）。对最终和的贡献将是n * b n * 2

n。您需要对每个位进行此操作，并将所有这些贡献加在一起。

可以在O（kn）时间中完成，其中O k是给定值中的位数。

以上是 所有对的异或值之和 的全部内容， 来源链接： utcz.com/qa/403935.html