基础知识

  • 负数在计算机中是用补码来存储的，由于正数的补码就是原码，姑可以推广到所有的数在计算机中都是用补码来存储的。
  • 原码：就是数的二进制形式。负数的原码最高位是1，代表符号位。
  • 反码：正数的反码还是其本身，负数的反码是在原码的基础上，符号位不变，其余位按位取反。
  • 补码：正数的补码还是其本身，负数的补码在其反码的基础上加一。

代码实现

class Solution {
public:
     int  NumberOf1(int n) {
     	int ans=0;
     	while(n!=0)
     	{
            ans++;
            //消掉一个1
            n = n&(n-1);
     	}
     	return ans;
     }
};

小技巧
通过位运算公式 n & (n - 1)可以消去二进制n的最右边的一个一（小伙伴们可以自己手动计算一下，负数正数都试试）。其上述代码的思想就是不断消1，消一次使得计数器加一。最后使n变成零结束循环。

我提一嘴

可能有人会疑惑（我觉得应该有的吧-△-）， 整数转换为二进制的代码在哪儿呢？ 其实n&（n-1）的运算过程中计算机会自动将n转换为二进制计算的，（说转化不太严谨，n本来就是以二进制的形式存储在计算机中的）。