Program to find the Sum of bit differences among all pairs

Suppose we have an array of n integers, we have to find the sum of bit differences in all pairs that can be formed from array elements.

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

Examples:

Input: arr[] = {3, 5}

Output: 4

All pairs in array are (3, 3), (3, 5)

                       (5, 3), (5, 5)

Sum of bit differences = 0 + 2 +

                         2 + 0

                      = 4

Input:  arr[] = {3, 5, 8}

Output: 16

All pairs in array are (3, 3), (3, 5), (3, 8)

                       (5, 5), (5, 3) (5, 8),

                       (8, 8), (8, 3), (8, 5)

Sum of bit differences =  0 + 2 + 3 +

                          0 + 2 + 3 +

                          0 + 3 + 3 

                       = 16

There is a simple Solution in which we have to run two loops to consider all pairs one by one. For every pair, we have to count bit differences. Finally, return the sum of counts. 

Program in C

#include<stdio.h>

int count_Bit(int ,int );

void main() {

    int a[5],n,i,j,count=0;

    scanf("%d",&n);

    for(i=0;i<n;i++)

    scanf("%d ",&a[i]);

    for(i=0;i<n;i++)

    {

        for(j=0;j<n;j++)

        {

            count=count+count_Bit(a[i],a[j]);

        }

    }

    printf("%d",count);

}

 int count_Bit(int a,int b)

 {

  a=a^b;

  int count=0;

  while(a)

  {

      a=a&(a-1);

      count++;

  }

  return(count);

 }

INPUT:

3

3 5 8

OUTPUT:

16