所有对的异或值之和

所有对的异或值之和

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

例如，查看数组中所有数字的最右边。假设

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

是给定值中的位数。