本文共 1242 字，大约阅读时间需要 4 分钟。

原文地址：

例子：

输入: arr[] = {1, 2} 输出: 4 数组中所有的整数对：(1, 1), (1, 2) (2, 1), (2, 2) 位差异数之和 = 0 + 2 + 2 + 0 = 4 输入: arr[] = {1, 3, 5} 输出: 8 数组中所有的整数对：(1, 1), (1, 3), (1, 5) (3, 1), (3, 3) (3, 5), (5, 1), (5, 3), (5, 5) 位差异数之和 = 0 + 1 + 1 + 1 + 0 + 2 + 1 + 2 + 0 = 8

一个简单的想法就是跑上两个循环逐个考虑所有的整数对，对于每一个整数对，计算位的差异。最后返回差异数的总和。这种方法的时间复杂度是O(n^2)。

有一个有效的方法可以在O(n)的时间内解决这个问题，它的方法就是将所有的数字都用32位（或者是其他固定位数）表示。这个想法是计数单独位的差异。我们可以遍历0到31并计数第i位的置位。设这个计数是“count”。这里将有“n - count”个数字的第i位没有置位，所以第i位的差异数是“count * (n - count) * 2”

下面是基于上述想法的C++实现：

// C++ program to compute sum of pairwise bit differences#include 
   
    using namespace std;int sumBitDifferences(int arr[], int n){    int ans = 0;  // Initialize result    // traverse over all bits    for (int i = 0; i < 32; i++)    {        // count number of elements with i'th bit set        int count = 0;        for (int j = 0; j < n; j++)            if ( (arr[j] & (1 << i)) )                count++;        // Add "count * (n - count) * 2" to the answer        ans += (count * (n - count) * 2);    }    return ans;}// Driver prorgramint main(){    int arr[] = {
  1, 3, 5};    int n = sizeof arr / sizeof arr[0];    cout << sumBitDifferences(arr, n) << endl;    return 0;}
   

输出：

8

转载地址：http://ggqii.baihongyu.com/