政子的博客

技术|学习|随笔

CodingInterview-二进制中1的个数

注意 n 的右移会将最高位复制到右边，如果 n 为负数，那么就会出现死循环。死循环解法如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
     int  NumberOf1(int n) {
         int result=0;
         while(n!=0){
             if(n&1==1) result++;
             n>>=1;
         }
         return result;
     }
};

要避免死循环非常简单，可以将 n 转换为 unsigned int，解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
     int  NumberOf1(int n) {
         unsigned int m=(unsigned int)n;
         int result=0;
         while(m){
             if(m&1) result++;
             m>>=1;
         }
         return result;
     }
};

书中还有一个很神奇的解法：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
     int  NumberOf1(int n) {
         int result=0;
         while(n){
             result++;
             n=(n-1)&n;
         }
         return result;
     }
};

这个解法的关键有几点：

  1. 如果一个数字非 0，那么它的二进制位中至少包含一个 1
  2. 一个数字 -1 的操作就是将它离最低位最近的 1 变成了 0，而将该位后面的 0 变成了 1
  3. 将该数字与 -1 后的数字取且，就会得到一个新的数字，这个数字中将原来的最低为 1 的位右侧的所有位变成了 0

举一个例子就是：如果一个数字 n=12，那么它的二进制表示为 1100，那么 n-1 的二进制表示为 1011，n&(n-1)的二进制表示为 1000。这完全符合上述规律。