题解 | #二进制中1的个数#

这道题我是为了让自己加深映像，分析一下C++题解，因为我一开始的想法十分复杂：

1. 通过前面一道题solve()函数将数字M以N进制形式表示，先获取二进制字符串
2. 然后根据返回的字符串第一个字符是不是‘-’符号 进行分类讨论
3. 如果不是负号 直接数就可以
4. 如果是负号 那么先得到反码，再想办法得到补码 缺点： 很麻烦，负数的结果还不对

看了第一篇题解之后，才意识到本身正负数在计算机里就是按照反码存储的，同时位移运算会自动补全 方法1：二进制移位

int val;
int ans=0;
while(val!=0)
{
  if(val & 1) ++ans;
  val>>=1;
}

代码中缺点是如果val是正数，没问题，>> 移位运算之后最高位会自动补0；但是如果val是负数，>> 移位运算之后最高位自动补的是1，就会出现问题 因此有了如下优化：

int val;
int ans=0;
int mark=0x01;
while(mark!=0)
{
  if(mark & val) ++ans;
  mark<<=1;
}

方法2：技巧法 对于上面的解法，因为对于‘0’的位还是需要做判断，理想的优化是直接跳过 于是交了一个比较机智的办法：val & (val-1) 大家可以自己验算一下 比如val=1101000 val-1=1100111 那么val & (val-1) = 1100000 意味着可以捕获到低位的1 然后除去，继续向前

int val;
int ans=0;
while(val!=0)
{
  ++ans;
  val=val&(val-1);
}