Sum of bit differences among all pairs

Reference:

1. Sum of bit differences among all pairs

Sum of bit differences among all pairs

Given an integer array of n integers, find sum of bit differences in all pairs that can be formed from array elements. Bit difference of a pair (x, y) is count of different bits at same positions in binary representations of x and y.

For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 ( first and last bits differ in two numbers).

Examples:

Input: arr[] = {1, 2}
Output: 4
All pairs in array are (1, 1), (1, 2)
                       (2, 1), (2, 2)
Sum of bit differences = 0 + 2 +
                         2 + 0
                         = 4

Input:  arr[] = {1, 3, 5}
Output: 8
All pairs in array are (1, 1), (1, 3), (1, 5)
                       (3, 1), (3, 3), (3, 5)
                       (5, 1), (5, 3), (5, 5)
Sum of bit differences = 0 + 1 + 1 +
                         1 + 0 + 2 +
                         1 + 2 + 0 
                       = 8

1. My solution without survey:

我的作法如下:

• 首先排除自己與自己的比較((1,1), (3,3), (5,5))
• 在下面可以看到(1, 3), (1,5), (3, 5)各有兩個,所以我們只要各計算一次,再乘以二 *,然後把它加總起來,最後就是答案
• 時間複雜度:O(n^2)

(1, 1), (1, 3), (1, 5)

(3, 1), (3, 3), (3, 5)

(5, 1), (5, 3), (5, 5)

int BitDifferences(int a, int b)
{
    int n, nCount;

    nCount = 0;
    n = a ^ b;

    while(n) {
        nCount++;
        n = n&(n-1);
    }

    return nCount;
}

int sumBitDifferences(int *a, int n)
{
    int i, j, nSum;

    nSum = 0;

    for(i=0; i<n-1; i++) {
        for(j=i+1; j<n; j++) {
            nSum += (BitDifferences(a[i],a[j]) * 2);
        }
    }
    return nSum;
}

2. Awesome Method provided by GeeksforGeeks:

• All numbers are represented using 32 bits (or some fixed number of bits).
• The idea is to count differences at individual bit positions.
• We traverse from 0 to 31 and count numbers with i’th bit set.
• Let this count be count. There would be n-count numbers with i’th bit not set.
• So count of differences at i’th bit would be count * (n-count) * 2. (這裡乘2,就像我上面的第二步那樣)

• Time complexity of this solution : O(n)

  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;
  }