数组中满足位方程式的对数

Question

2*set_bits(XY)=M+set_bits(X(Y))

注：

• set_bits(n)表示整数n的二进制表示中1的个数。
• xy表示整数X和y的按位或。
• X？y表示整数X和y的按位异或。
• 无序数组元素对是对(Ai,Aj)，其中1≤i

Answer 1

如果set_bits的时间复杂度为O(1)，则存在时间复杂度O(n)的解决方案。

首先，我们将对这个条件（按位方程）进行稍微修改。假设给定一对元素(X，Y)。设C_01表示X为0但Y为1的位数，C_10表示X为1且Y为0的位数，C_11表示X和Y为1的位数。例如，当x=5和y=1(x=101,y=001)时，c_01=0，c_10=1，c_11=1。现在，条件可以重写为

2 * (c_01 + c_10 + c_11) = M + (c_01 + c_10)

因为set_bits(XY)等于C_01+c_10+C_11和set_bits(x^y)等于C_01+c_10。我们可以把方程重新排序为

c_01 + c_10 + 2*c_11 = M

把右边的项移到左边。现在，认识到set_bits(X)=c_10+C_11。将这些信息应用到我们得到的方程上

c_01 + c_11 = M - set_bits(X)

现在，还要认识到set_bits(Y)=c_01+c_11。等式变成

set_bits(Y) = M - set_bits(X)

或

set_bits(X) + set_bits(Y) = M