劍指 Offer 15. 二進制中1的個數-每日一題

一、題目

  請實作一個函數，輸入一個整數（以二進制串形式），輸出該數二進制表示中 1 的個數。例如，把 9 表示成二進制是 1001，有 2 位是 1。是以，如果輸入 9，則該函數輸出 2。

點選檢視原題

難度級别： 簡單

二、 思路

1）按位運算

  由于給定的是

32

位

int

型資料，需要計算二進制位中所有

1

的個數，可以去位移并判斷每一位是否為

1

，進行計數

2）數學方法

  采用

n &= n-1

的方式消去

n

中存在的

1

，原理（舉例）如下：

n = 0000 0000 0000 1100

n-1 = 0000 0000 0000 1011

n & (n-1) = 0000 0000 0000 1000

  因為

n-1

會消去最低位的

1

，進行與運算，就消去了最低位的

1

三、代碼

1）按位運算

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            if ((n & 1) == 1) {
                ans++;
            }
            n = n >>> 1;
        }
        return ans;
    }
}
           

  

n

為

32

，時間複雜度為

O(n)

，空間複雜度為

O(1)

2）數學方法

public class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        while (n != 0) {
            n &= n-1;
            ans++;
        }
        return ans;
    }
}
           

  

n

為

32

，時間複雜度為

O(logn)

，空間複雜度為

O(1)