面试题：找出一个整数的二进制中1的个数

summary

:

很经典的一道题，而且是很多位运算的题目的鼻祖，掌握它，很多问题的变种就可以解决 了。

题目

实现一个函数，输入一个整数，返回这个整数的二进制表示中1的个数。

分析

对于正数和0，很简单，先和0x1进行与运算，如果结果是1,则最低位是1。然后不断右移， 进行相同的判断，直到这个数变成0为止。

但是对于负数，就不能像上面那样做了，因为右移的话，左边会补1,则无法判断什么时候 结束了。这样有两种方法：

• 对于负数，规定右移31次就结束。
• 对于负数，先用0x1和这个数进行与运算，然后把0x1左移一位，变成了0x2，再进行 与运算，直到变成了0。这样也是移动了31次。

更好的方法

有一个非常好的办法，看了顿时感觉想出来的人太聪明了。那就是不断将这个数减去1与 原数做与运算，最后这个数会变成0。进行了多少次这样的操作，就有多少个1。比如， 10000100，减去1之后变成了10000001，10000100 & 10000001 = 10000000， 10000000减去1之后变成01111111，与操作之后变成了0，则只有2个1。

代码

::: {.code-include lexer="cpp"} ./times-of-one-in-binary-integer.cpp :::

使用了Boost的单元测试框架，链接的时候要加上 -lboost_unit_test_framework 参数。