JZ11 二進制中1的個數 python

JZ11 二進制中1的個數

my version

未通過所有樣例，記憶體超過限制記憶體

class Solution:
    def NumberOf1(self, n):
        if n >= 0:
            symbol = 0
        else:
            symbol = 1
        binary = []
        while n:
            binary.append(n % 2)
            n = n // 2
        if n < 0:
            # 獲得完整二進制
            add_0 = 32-len(binary)-1
            for i in range(add_0):
                binary.append(0)
            # 符号位
            binary.append(1)
            # 除符号位取反
            for i in range(len(binary)-1):
                binary[i] = binary[i] ^ 1
            for i in range(len(binary)):
                binary[i] = binary[i] ^ 1
                if binary[i]^1 == 1:
                    break
        return sum(binary)
           

book method1

通過位運算和位移操作 題目轉變為判斷最右邊的一位是否為1,但這種做法在判斷負數時會出錯，是以用數字n與1做位運算，判斷最右邊後将1左移，依次判斷

python沒有位數的概念

以下為C++代碼

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         unsigned int flag = 1;
         while(flag){
             if(n & flag)
                 count++;
             flag = flag << 1;
         }
         return count;
     }
};
           

把一個整數減1後再和原來的數做位與運算，相當于把該整數的最右邊的1變為0

class Solution {
public:
     int  NumberOf1(int n) {
         int count = 0;
         while(n){
             n = (n-1)&n;
             count ++;
         }
         return count;
     }
};