Eisen 筆記

#191. Number of 1 Bits

題目描述

寫一個函式處理無符號整數(unsigned integer)，然後回傳位元為'1'的數量。

  • 在某些程式語言中，像是JAVA。沒有無符號整數的型別。在這種情況下，輸入會是有符號的整數型別。但是這不應該影響到整個函式的實作結果，不論有無符號，整數的二元表示都是一樣的。
  • 在JAVA中，符號整數使用二進制補碼。

限制條件

  1. 輸入是長度為32的用來表示二進制數值的字串。

解題思路

限制條件是Test Case的輸入條件，但是函式的實際輸入為整數，因此不用在函式內處理字串。

Intuition

在十進制中，整數的偶數在二進位中的尾數都會是0，而奇數會是1。 因此只要使用模除來判定尾數是否為1，並且搭配位元右移來把左邊的位元往右移，就可以不斷的判斷位元值直到全部為0為止。

public class Solution { 
	public int HammingWeight(uint n) {
        int c = 0;
        while(n!=0){
            if(n%2==1) c++;
            n>>=1;
        }
        return c;
    }
}

複雜度分析：

  • 時間複雜度：由於是32位元，while迴圈最多執行32次就結束了，因此時間複雜度為O(1)。
  • 空間複雜度：空間複雜度為O(1)。

Follow-up

如果這個函式會被呼叫很多次，你要怎麼去改善它？

Optimized

如果會被呼叫很多次，每一次呼叫都會計算肯定是比較花費時間的，因此要建立快取讓答案可以快速被取得。 參考338.Counting Bits的方法，透過取得之前計算的結果來快速計算新的答案。 我們將32位元分成兩個16位元，先計算前16位元每個值的bit數量，然後存入快取之中，超過16位元的部分會是16位元內的數值的組合。

Solution的建構式在Leetcode中是受保護的，因此沒辦法在Leetcode中測試C#。

public class Solution { 
    int len=0;
    int[] pre_ans;    
    Solution(){
        len = 1<<16;
        pre_ans = new int[len];
        PreCompute();
    }
    public int PreCompute(){
        for(int i=0;i<len;i++){
            pre_ans[i] = pre_ans[i>>1]+ i%2;
        }
        return 0;
    }
    public int HammingWeight(uint n) {        
        return pre_ans[n/len] + pre_ans[n%len];
    }
}

複雜度分析：

  • 時間複雜度：時間複雜度為O(1)，但在大量呼叫的情況下，排除重新建立實例再呼叫的行為，執行的速度會快於每一次呼叫都進行計算。
  • 空間複雜度：事先建立了一部分空間用來存放快取，但在執行時不會增加使用空間，因此空間複雜度為O(1)。

學習重點

  • 位元操作
  • 分治法(Divide And Conquer)
Last Updated:
Contributors: eisen