《剑指offer刷题笔记》14、二进制中1的个数【c++详细题解】

Dear 丶 2021-07-24 20:28 341阅读 0赞

### **题目** ###

输入一个  32 32 32 位整数，输出该数二进制表示中  1 1 1 的个数。

**注意**：

*  负数在计算机中用其绝对值的补码来表示。

**样例1**

输入：9
    输出：2
    解释：9的二进制表示是1001，一共有2个1。

**样例2**

输入：-2
    输出：31
    解释：-2在计算机里会被表示成11111111111111111111111111111110，
          一共有31个1。

### **思路1** ###

l o w b i t ( x ) lowbit(x) lowbit(x)**函数的作用**

l o w b i t ( x ) lowbit(x) lowbit(x)**操作返回  x x x 的最后一位  1 1 1**

*   x = 101 0 2 x=1010\_2 x=10102，那么  l o w b i t ( x ) lowbit(x) lowbit(x) 返回  1 0 2 10\_2 102，即 l o w b i t ( x ) = 10 lowbit(x)=10 lowbit(x)=10
 *   x = 10100 0 2 x=101000\_2 x=1010002，那么  l o w b i t ( x ) lowbit(x) lowbit(x)返回 100 0 2 1000\_2 10002，即 l o w b i t ( x ) = 1000 lowbit(x)=1000 lowbit(x)=1000

**l o w b i t lowbit lowbit 的应用：可以统计  x x x 中  1 1 1 的个数**

就是每一次把  x x x 的最后一位  1 1 1 减掉，即  x − l o w b i t ( x ) x−lowbit(x) x−lowbit(x)，只需要算下减多少次，减多少次就有多少个 1 1 1 。

### **代码1** ###

class Solution { 
    public:
        int lowbit(int x)
        { 
            return x&-x;  //返回二进制中最后一位1
        }
        int NumberOf1(int n) { 
            int res = 0;
            while(n)
            { 
                n -= lowbit(n);
                res++;
            }
            return res;
        }
    };

### **思路2** ###

**(位运算)**  O ( l o g n ) O(logn) O(logn)  
迭代进行如下两步，直到  n n n 变成 0 0 0为止：

1.  如果  n n n 在二进制表示下末尾是1，则在答案中加1；
2.  将  n n n 右移一位，也就是将  n n n 在二进制表示下的最后一位删掉；

这里有个难点是如何处理负数。  
在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致  n n n 永远不为0，就死循环了。  
解决办法是把  n n n 强制转化成无符号整型，这样  n n n 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。

**时间复杂度**  
每次会将 n n n 除以 2 2 2，最多会除  l o g n logn logn 次，所以时间复杂度是  O ( l o g n ) O(logn) O(logn)。

### **代码2** ###

class Solution { 
    public:
        int NumberOf1(int n) { 
            int res = 0;
            unsigned int un = n; 
            while (un) res += un & 1, un >>= 1;
            return res;
        }
    };