【剑指offer】 面试题15 二进制中1的个数

面试题–【剑指Offer】 题目解答

补充知识：

由于本题涉及到一些位运算的知识，所以在最开始简单的介绍一下。

位运算

位运算是把数字用二进制表示之后，对每一位上的0或1的运算。二进制是指数字的每一位都是0或者1。如十进制的2转换成二进制就是10。

位运算常用的五种运算：包括与(&)，或(|)，异或(^)，左移(<<)，右移(>>)。

这里说一下，左移运算要把数字在右端补上0:如00001010 <<2 = 00101000

右移运算要把数字在左端补上0（数为正数时）如00001010>>2 = 00000010

右移运算要把数字在左端补上1（数为负数时）如10001010>>2 = 11100010

题目要求

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

解题思路

根据题目要求和补充知识的介绍，在这里我们给出三种解题思路，大家可以比较来看。

（1）用输入的数的每一位和1做与运算，统计结果为1的数量，即是结果。这里边难点是如何统计每一位的位运算结果？使用右移操作，把输入的数每次右移一位和1做与运算，然后依次统计每次循环的结果。这里有个问题，根据补充知识的介绍我们知道，当输出是负数的时候，右移操作需要在左边补上1而不是0，如果一直补0，很可能会造成死循环。所以不建议使用这种做法。

（2）常规解法：我们尽量比避免在位运算中进行右移操作。在不改变输入数据的情况下，用一个变量不断向左移和原数据进行与运算。（如用1（1）去判断最低位，用2（10）去判断倒数第2位，用4（100）去判断倒数第3位······以此类推）

优点:简单，好理解。

缺点:当输入数据的二进制位数越大时，进行比较的次数越多。（100位比较100次） 有没有比较少一点的方法？

（3）惊喜解法：有几个1就比较几次的方法！！！以1100为例，我们先对其做一个减1的操作，得到：1011。然后再和原数据(1100)进行与运算，得到结果：1000 。这个结果实际上就是把原数据(1100)的最右边一个1变成了0。继续上边的操作，得到结果0000。结束，可以得到原数据中有2个1。一共比较2次。

注意 ：把一个整数减去1之后再和原来的整数进行位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成了0，很多二进制的位运算用到了这个结论！！！

主要代码c++

常规解法

class Solution {
public:
     int  NumberOf1(int n) {
         int count =0;
         int flag = 1;//检测变量
         while(flag)
         {
         	if(flag&n) //检测位是1
             	count++;
             flag = flag<<1; // 左移变量
         }
         return count;
     }
};
           

惊喜解法

class Solution {
public:
     int  NumberOf1(int n) {
         int count =0;
         while(n)
         {
             count++;
             n = (n-1)&n; // 整数减1再和整数做位与运算
         }
         return count;
     }
};
           

总结扩充

注意 ：把一个整数减去1之后再和原来的整数进行位与运算，得到的结果相当于把整数的二进制表示中最右边的1变成了0，很多二进制的位运算用到了这个结论！！！

相关题目：

1、用一条语句判断一个整数是不是2的整数次方？

答：一个整数是2的整数次方如4，8那么在二进制表示中有且只有一个1，我们只需要把这个整数减去1再和他自己做位于运算，这个整数的1就会变成0。

n&(n-1)=0 2、输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。比如10的二进制（1010），13的二进制（1101）。

答：分两步，我们首先先计算这两个数有几位是不同的，用异或运算即可。第二步统计异或运算结果中有几个1就可以知道两个数有几位是不同的。