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;
     }
};