# 2020q3 Homework4 (quiz4)
contributed by < `johnnycck` >

## 測驗一
此題需要完成可以實作出兩整數的 Hamming distance。

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

* ans: OP = ^，因為要算 Hamming Distance，使用 ^ ，兩者相異才會顯示出來，再透過 __builtin_popcount( )，得到有幾個 '1'，及是 Hamming Distance。
:::success
延伸問題:
練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
:::
* 我試圖提交上面程式碼的延伸，但卻得到 TLE (Time Limit Exceeded)

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}
int totalHammingDistance(int* nums, int numsSize){
    int ans=0;
    for(int i=0; i<numsSize; i++) {
        for(int j=i+1; j<numsSize; j++) {
            ans += hammingDistance(*(nums+i),*(nums+j));
        }
    }
    return ans;
}

* 經過嘗試後，發現寫不出來，因此去看別人的 discussion，我參考了其中一個解答

int totalHammingDistance(int* nums, int numsSize) {
    /*
        record each bit 1's number,
        each bits total hamming distance: countone*(numsSize - countone)
    */
    int count_one = 0;
    int number = 0;
    /*32(can decrease to least 30) bits is enough to repreent 10^9*/
    for(int i = 0;i < 30;i++)
    {
        /*init count_one of each bits*/
        count_one = 0;
        for(int j = 0;j < numsSize;j++)
        {
            if(nums[j]&1 == 1)
            {
                count_one++;
            }
            nums[j] = nums[j] >> 1;
        }
        number = number +  count_one * (numsSize - count_one);
    }
    return number;
}

* 解釋程式碼流程:
1. 他的解法是一次比對同一個 Bit Position 的全部 input，假設 input 是 4, 14, 2，以二進為表示就是

* | Input \ Bit Position | 3 | 2 | 1 |0 |
| -------- | -------- | -------- |-------- |-------- |
|4| 0 | 1 | 0 |0 |
|14| 1 | 1 | 1 |0 |
|2| 0 | 0 | 1 | 0 |
2. 先比對 Position 0，把有 '1' 的個數跟有 '0' 的個數相乘，最後再將每個 Position 的答案相加 (i 設為 32 是因為 input 最大是 10^9，不過 30 其實就可以表達 10^9)
1. 以此題為例，可以得到 2 + 2 + 2 + 0
* 原先我的思考流程就是要將所有的 input 都相互比過一次，但這樣時間複雜度會是 O(N^2)，較佳的解法是以 position 的方式，將每個 input 的同一個 position 比對過，再相加起來，而這個動作可以由 '1' 的個數跟 '0' 的個數相乘得到，這是因為 '1' 的個數代表同一個 '0' 會跟幾個 1 產生 hamming distance，而 '0' 的個數就代表有幾個前述的 '0'，所以相乘就會是某個 position 的總 hamming distance