LeetCode题目：191. 位1的个数

三种方法：

1. 常规的方法，每次遍历二进制数中的一位，如果为1则count += 1，这里每次遍历的时候都会采用左移或者右移，但是要注意一个坑, 如果是一个有符号的数，每次右移之后都会不上符号位，因此对于一个有符号的负数，将会一直补上1，只到最后数字变为0xffffffff, 只会陷入死循环， 但是题目中说了是无符号整数，因此我们可以右移。Tips:如果面试官问右移或者左移运算改成除法或者乘法，是不可行的，因为计算机对于位运算的效率远远高于除法或乘法，所以我们平常用乘或除以特定数字的时候可以采用位运算来提升速度，时间复杂度：int对应计算机的位数
2. 面试官最喜欢的方法：x = x & (x – 1) 例如对于二进制 10100 将会直接跳过后两个0到最后一个1所在的位置 时间复杂度：二进制表示中1的个数
3. 自己总结：该方法针对于Python的，先将一个数字转换为二进制，之后转换为字符串，然后遍历字符串中的每一位，统计1的个数，发现竟然比方法2效率还高，Python内置函数还是强啊 时间复杂度：int对应计算机的位数

剑指offer中的内容：

面试官最喜欢的方法

# 方法一：对于该题右移不会出现bug,因此我们可以右移
class Solution(object):
    def hammingWeight(self, n):
        count = 0
        while n != 0b00:
            # 如果最后一位为1, 否则是不会count+1
            if n & 1:
                count += 1
            n = n >> 1
        return count

这里使用c语言实现方法一的左移版本，不使用python原因：因为python的int类型字节数比其他语言的int字节数多， 因此移动次数将会很多，我这里使用python实现的时候发现陷入了死循环

陷入死循环的代码：

class Solution(object):
    def hammingWeight(self, n):
        count = 0
        temp = 1
        while temp:
            if n & temp:
                count += 1
            temp = temp << 1
        return count

中间额外加了一个变量，循环超过32次则结束，还是有一定的缺陷

class Solution(object):
    def hammingWeight(self, n):
        count = 0
        temp = 1
        t = 0
        while temp:
            t += 1
            if n & temp:
                count += 1
            temp = temp << 1
            if t >= 32:
                break
        return count

如下代码查看Python中的int的字节数

import sys
print(sys.getsizeof(5))  # 28
print(type(5))  # <class 'int'>

// 剑指offer左移
int NumberOf(int n)
{
    int count = 0;
    unsigned int flag = 1;
    while(flag)
    {
        if(n & flag)
            count ++;
        flag = flag << 1;
    }
}


// 自己代码
#include <stdio.h>
int main()
{
    int n = 4096;
    int temp = 1;
    int count = 0;
    while (temp)
    {
        if (n & temp)
            count += 1;
        temp = temp << 1;
    }
    printf("%d\n", count);
    return 0;
}

# 方法二
class Solution(object):
    def hammingWeight(self, n):
        count = 0
        while n != 0:
            count += 1
            n &= (n - 1)
        return count

# 方法三
class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int 要求二进制中1位数的数
        :rtype: int 返回二进制中数字1的位数
        """
        return bin(n).count('1')