题目

请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。

思考

小甜点：计算机为什么要用0和1？
0，1是一种计数方式。
为什么是二进制，而不选择十进制。是因为计算机构造决定的。
计算机的构造：计算机核心是芯片，芯片由上亿个微小的晶体管构成。晶体管的两种状态可以分别表示0，1。任意数量的晶体管就可以表示任何数。比如8个晶体管排成一列，就可以表示0~255共256个数字。
所以说用二进制，不用其他进制。

左移运算：m << n，表示把m左移n位。在左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。
右移运算：m >> n，表示把m右移m位。在右移n位的时候，最右边的n位将被丢弃。如果是无符号的数字，则用0填补最左边的n位；如果是有符号的数值，则用数字的符号位填补最左边的n位。
例：
00001010 >> 2 = 00000010
10001010 >> 3 = 11110001
**
每次和1按位与，如果为1，则count + 1；否则，count不变。整数右边移一位。
结束条件：

  • 正数，符号位为0，如果这个整数为0，结束循环
  • 负数，符号位为1，就会进入死循环。

如何判断每一位是不是1？
每次把n和1做与运算，接着把1左移判断下一位是不是1。
输入的是整数，如果是c++，整型占4个Byte，共32位，最多循环32次。
python中不行，python中的整型可以支持任意大小。

重点：把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0。
n有多少个1，就进行多少次与操作。

代码

  1. class Solution:
  2.     def hammingWeight(self, n: int) -> int:
  3.         count= 0
  5.         while n & 0xffffffff != 0:
  6.             n &= (n - 1)
  7.             count += 1
  8.         return count

image.png

n & 0xffffffff ：得到32位的二进制补码。
数在计算机中是以补码的形式存在，正数的补码与原码一致。
负数的补码是反码，再加1。

扩展

一条语句判断一个整数是不是2的整数次方。
分析：如果一个整数是2的整数次方，那么它的二进制表示中有且只有一位是1。

  1. def is_square_2(n):
  2.     return n & (n - 1) == 0

输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。

  1. def digitCountFromM2N(m, n):
  2.     tmp = m ^ n
  3.     count= 0
  5.     while tmp > 0:
  6.         tmp &= (tmp - 1)
  7.         count += 1
  8.     return count