剑指offer面试题[10]-二进制中1的个数

àì夳堔傛蜴生んèń 2022-06-13 00:21 122阅读 0赞

## 题目描述 ##

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

分析：

这是一道很基本的考察二进制和位运算的面试题。思路：先判断证书二进制表示中最右边的一位是不是1。接着再把输入的数字右移一位，此时原来处于从右边数起的第二位被移到了最右边了，再判断是不是1.这样每次移动一位，直到整个整数变成0为止。现在的问题变成怎么判断一个整数的最右边是不是1了。这很简单，只要**把整数和1做按位与运算**看结果是不是1就行了。1除了最右边的一位外所有位都是0.如果一个整数与1做与运算的结果是1，表示该位最右边一位是1，否则是0。于是我们很快写出了代码（有漏洞，可能导致死循环）。

class Solution\{

punlic:

int NumberOf1(int n) \{

int count=0;

while(n)

if(n&1)

count++;

n>>1;

return count;

注意：右移运算与除以2在结果上是等价的，但是除法的效率是**远远低于**移位运算的。

那么问题来了，如果输入一个负数呢？比如0x80000000，运行的时候会出现什么状况呢？把负数0x80000000右移一位的时候，并不是简单地的把最高位的1移到第二位变为0x40000000，而是0xc0000000。这是因为移位前是个负数，移位后要保证仍然是个负数，因此移位后的最高位会设为1。如果一直做右移运算，最终这个数字就会变成**0xFFFFFFFF而陷入死循环**。

为了避免死循环，我们可以不右移输入的数字n。首先把n与1做与运算，判断n的最低位是不是1.接着把1左移一位得到2，再和n做与运算，判断n的次低位是不是1......1逐渐变为2、4、8、....代码如下：

class Solution \{  
public:  
     int  NumberOf1(int n) \{   
         int count=0;  
         unsigned int flag=1;  
         while(flag)  
            \{   
               if(n&flag)  
                  count++;  
               flag=flag<<1;  
            \}  
         return count;  
     \}  
\};