剑指offer学习笔记——位运算1：统计二进制中的1的个数

112 阅读 0 评论 74 点赞

我是靠谱客的博主儒雅水壶，这篇文章主要介绍剑指offer学习笔记——位运算1：统计二进制中的1的个数，现在分享给大家，希望可以做个参考。

二进制相对于十进制来说总是比较抽象的。

例题：对于给定一个整数，要求统计整数中的二进制个数。

这个题有一个常规的思路就是我们统计这个整数最后一位是不是1，然后再将其右移移位。但是由此出现了一个严重的问题，如果是负数的话，右移之后前面时补1的，而不是补0。所以除非实现规定好右移多少次（4个字节 32次），否则，如果整数是否变为0来作为循环判断的话是会陷入死循环。

以此为启发，我们不移动整数了。以此判断从末尾到首位一共有多少个1：

复制代码

1
2
3
4
5
6
7
8
9
10
11
int  NumberOf1(int n) {
         int count = 0;
         unsigned int flag = 1;
         while(flag)     //循环结束条件一个关键的点，无符号的int在移位32次（32位，4个字节）后，会变成0
         {
             if(n&flag)
                 count++;
             flag<<=1;
         }
         return count;
     }

另外一个方法是减去1，整数中有多少位1就循环多少次，十分简洁：

复制代码

1
2
3
4
5
6
7
8
9
    int  NumberOf1(int n) {
         int count = 0;
         while(n)     //循环结束条件一个关键的点，无符号的int在移位32次（32位，4个字节）后，会变成0
         {
             n = (n-1)&n;//这个运算每做一次就会使得二进制中的1少一个
             count++;
         }
         return count;
     }