[477] Total Hamming Distance

Hamming Distance 是什麼新潮的玩意兒 XDDD

用直覺寫的雖然是對的但果不其然的超時了 XD (雖然一開始算了兩次，多算了 XP）

先貼一下

int totalHammingDistance(int* nums, int numsSize){

int count = 0;

for (int i=0;i<numsSize-1;i++)

{

for (int j=i+1;j<numsSize;j++)

{

int tmp= nums[i] ^ nums[j];

while (tmp >0)

{

count += (tmp & 0x1);

tmp = tmp>>1;

}

}

}

return count;

}

然後聽說是要直接算每個 bit 是1 的個數 和是 0 的個數 相乘！！！

（唉數學真是麻煩）

所以就會變成這樣: 

int totalHammingDistance(int* nums, int numsSize){
    int *count = calloc (32, sizeof(int));
    int ret=0;
    for (int i=0;i<32;i++)
    {
        for (int j=0;j<numsSize;j++)
        {
            int tmp = nums[j]& 0x1;
            count[i] += tmp;
            nums[j]= nums[j]>>1;
        }
        ret += (count[i]* (numsSize-count[i]));
    }
    return ret;
}

又，其實根本不需要用array 去存！！！ 所以終極版是這樣: 

int totalHammingDistance(int* nums, int numsSize){

int ret=0;

for (int i=0;i<32;i++)

{

int count=0;

for (int j=0;j<numsSize;j++)

{

count += nums[j]& 0x1;

nums[j]= nums[j]>>1;

}

ret += (count * (numsSize-count));

}

return ret;

}