algorithm - 最近谷歌关于按位运算的面试难题

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 异或 1 = 0
1 异或 1 = 0
1 异或 0 = 1
1 异或 0 = 1
1 异或 1 = 0
1 异或 0 = 1
1 异或 1 = 0

可以看出，该位的贡献是“关闭”位的数量。对于任何其他“开启”位也是如此。我们可以说每个“开”位都算作“关”位的数量：

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

乘以 2 是从哪里来的？好吧，因为我们对“off”位做同样的事情，除了这些，贡献是“on”位的数量：

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

这当然和上面一样，我们可以乘...

复杂度为O(n*k)，其中k是位数（代码中为 32）。

Answer 2

#include <bits/stdc++.h>
#define MOD 1000000007ll
using namespace std;
typedef long long LL;

int solve(int arr[], int n) {

    int ans = 0;
    // traverse over all bits
    for(int i = 0; i < 31; i++) {

        // count number of elements with ith bit = 0
        long long count = 0;
        for(int j = 0; j < n; j++) if ( ( arr[j] & ( 1 << i ) ) ) count++;

        // add to answer count * (n - count) * 2
        ans += (count * ((LL)n - count) * 2ll) % MOD;
        if(ans >= MOD) ans -= MOD;
    }

    return ans;
}

int main() {

    int arr[] = {1, 3, 5};
    int n = sizeof arr / sizeof arr[0];
    cout << solve(arr, n) << endl; 
    return 0;
}