“求和式(X3)”的解法

题目大意是这样的:

给定长度为n的序列A[i],求所有A[i] xor A[j] (i<j)的值之和。

如序列:7 3 5

转化为二进制
7:111
3:011
5:101

一位一位计算
7 xor 3+3 xor 5+7xor 5
(二进制)
=(100 xor 000)+(10 xor 10)+(1 xor 1)  //7 xor 3
+(000 xor 100)+(10 xor 00)+(1 xor 1)  //3 xor 5
+(100 xor 100)+(10 xor 00)+(1 xor 1)  //7 xor 5
按列计算
就变成乘法了:1+1+0=2*1=2
                    0+1+1=2*1=2
                0+0+0=0*1=0
再加权:2*4+2*2+0*1=12
现在的问题是如何快速计算每一列(位)的值?

可以发现只有0和1组合xor才可能产生 1,于是每列 1的个数就是这一列1的个数*0的个数。

结果就是   ∑(1<<i)*第i列1的个数*第i列0的个数

原文地址:https://www.cnblogs.com/wuminye/p/2752203.html