# Compute the hamming distance of an array of integers using their binary representation

• The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different (https://en.wikipedia.org/wiki/Hamming_distance). In the case of integers, you have to use their binary representation as strings.
For example:
3 = "11"; 1 = "01"; HammingDistance(3,1) = 1;
93 = "1011101"; 73 = "1001001"; HammingDistance(93, 73) = 2;
You can observe that it's the number of bits set after an XOR operation between two integers. But doing the same operation for n integers is too slow. You have to observe that it's the sum of multiplication of number of bits set by number of bits unset for each i bit where 0<i<sizeof(int)

Here is an O(n) solution in C#

``````public int HammingDistance(int[] input)
{
// the result is the number of 1 bits x number of 0 bits
int total = 0;
if (input != null && input.Length > 1)
{
// Counts number of bits set per position
int[] onebitscounter = new int[32];
for (int i = 0; i < input.Length; ++i)
{
int j = 0;
while (input[i] != 0)
{
if (input[i] % 2 == 1)
onebitscounter[j] += 1;
// shift one bit to the right
input[i] = input[i] >> 1;
++j;
}
}

for (int k = 0; k < 32; ++k)
{
total += onebitscounter[k] * (input.Length - onebitscounter[k]);
}
}