这是从谷歌最近的一次采访问题：

This is a recent interview question from Google:

我们定义F（X，Y）作为二进制不同的相应的比特数   重新X和Y的presentation例如，F（2,7）= 2，因为二进制   重的2和7 presentation是010和111，分别。在第一和   第三比特不同，所以F（2,7）= 2。

We define f(X, Y) as number of different corresponding bits in binary representation of X and Y. For example, f(2, 7) = 2, since binary representation of 2 and 7 are 010 and 111, respectively. The first and the third bit differ, so f(2, 7) = 2.

正在给定的N个正整数，A1，A2，...，AN的阵列。查找总和   F（艾，AJ）对于所有对（I，J），使得1≤I，J≤ñ

You are given an array of N positive integers, A1, A2 ,…, AN. Find sum of f(Ai, Aj) for all pairs (i, j) such that 1 ≤ i, j ≤ N

例如：

A = [1，3，5]

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）=

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

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

我觉得这个解决方案，它为O（N ^ 2）

I could think of this solution which is 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]);
   }
}

另一种方法我能想到的是（考虑到每个元素只包含一个二进制数）：

Another approach i can think of is (considering that each element contains only one binary digit):

从数组的末尾开始 在保持1的计数和0的发现迄今 如果当前元素是1，那么它将有助于 count_of_zeros 的最后一笔 在继续这样下去，直到我们达到了数组的开始。 Start from the end of the array keep a count of 1's and 0's found so far If the current element is 1, then it will contribute count_of_zeros to the final sum Continue like this till we reach the start of the array.

时的这种做法是正确的。

Is this approach correct.

推荐答案

迭代阵列，和上位的每个位的索引数的数，例如 [1，3，5]

Iterate the array, and count number of "on" bits in each bit index, for example [1, 3, 5]:

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

现在，每个位计数器，计算：

Now, for each bit counter, calculate:

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

[bit count] * [array size - bit count] * 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。如果我们检查第一个比特与阵列中的所有位（包括自，如在问题），我们得到：

To show why this works, lets look at a subset of the problem, using a single bit. Let's see what happens if we have an array with: [1, 1, 0, 0, 1, 0, 1]. Our count is 4 and size is 7. If we examine the first bit with all the bits in the array (including self, as in the question), we get:

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

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

如可以看到的，该位的贡献是是的关闭位的数目。同样适用于任何其他的上位。我们可以说，每一个上位计数为关闭位数：

As can be seen, the contribution of this bit is is the number of "off" bits. The same holds true for any other "on" bit. We could say that each "on" bit counts as the number of "off" bits:

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

[bit count] * [array size - bit count]

和哪里的乘以2从何而来？好，因为我们做同样的关位，不同之处在于对这些的贡献是开启位的数目：

And where does the multiplication by 2 comes from? well, since we do the same with the "off" bits, except that for these, the contribution is the number of "on" bits:

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

[array size - bit count] * [bit count]

这当然是与上述相同，这样我们可以只乘...

which of course is the same as above, and we can just multiply...

复杂性是 O（N * K）的，其中的 K 的是（在code 32）的位数。

Complexity is O(n*k) where k is number of bits (32 in your code).