最近谷歌采访按位操作拼图

Question

这是谷歌最近的采访问题:

我们将f(X,Y)定义为X和Y的二进制表示中的不同对应位的数量.例如,f(2,7)= 2,因为2和7的二进制表示分别是010和111.第一和第三位不同,因此f(2,7)= 2.

你得到一个N正整数的数组,A1,A2,...,AN.求所有对(i,j)的f(Ai,Aj)之和,使得1≤i,j≤N

例如:

A = [1,3,5]

我们回来

f(1,1)+ f(1,3)+ f(1,5)+ f(3,1)+ f(3,3)+ f(3,5)+ f(5,1)+ f (5,3)+ f(5,5)=

0 + 1 + 1 + 1 + 0 + 2 + 1 + 2 + 0 = 8

我能想到这个解决方案是O(n ^ 2)

int numSetBits(unsigned int A) {
    int count  = 0;

    while(A != 0) {
        A = A & (A-1);
        count++;
    }

    return count;
}

int count_diff_bits(int a, int b)
{
    int x = a ^ b;

    return numSetBits(x);
}

for (i = 0; i < n; i++)
   for (j = 0; j < n; j++) {
       sum += count_diff_bits(A[i], A[j]);
   }
}

我能想到的另一种方法是(考虑到每个元素只包含一个二进制数字):

• 从数组的末尾开始
• 保持到目前为止发现的1和0的计数
• 如果当前元素为1,则它将count_of_zeros对最终总和做出贡献
• 像这样继续,直到我们到达阵列的开始.

这种方法是否正确.

Answer 1

迭代数组,并计算每个位索引中"on"位的数量,例如[1,3,5]:

0 0 1
0 1 1
1 0 1
-----
1 1 3

现在,对于每个位计数器,计算:

[位数]*[数组大小 - 位数]*2

和所有位的总和......

以上示例:

3 * (3 - 3) * 2 = 0
1 * (3 - 1) * 2 = 4
1 * (3 - 1) * 2 = 4
          total = 8

为了说明其工作原理,让我们使用一位来查看问题的一个子集.让我们来看看,如果我们有一个数组会发生什么:[1, 1, 0, 0, 1, 0, 1].我们的计数是4,大小是7.如果我们检查数组中所有位的第一位(包括self,如问题中所示),我们得到:

1 xor 1 = 0
1 xor 1 = 0
1 xor 0 = 1
1 xor 0 = 1
1 xor 1 = 0
1 xor 0 = 1
1 xor 1 = 0

可以看出,该位的贡献是"关闭"位的数量.任何其他"on"位也是如此.我们可以说每个"on"位都算作"off"位的数量:

[位数]*[数组大小 - 位数]

2的乘法来自何处？好吧,因为我们对"off"位做同样的事情,除了对于这些,贡献是"on"位的数量:

[数组大小 - 位数]*[位数]

这当然与上面相同,我们可以繁殖......

复杂度为O(n*k),其中k是位数(代码中为32).