二进制中1的个数（Java实现）

89 阅读 0 评论 59 点赞

我是靠谱客的博主体贴铃铛，这篇文章主要介绍二进制中1的个数（Java实现），现在分享给大家，希望可以做个参考。

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

解题思路
首先要熟悉二进制的位运算：
&是与操作，|是或操作，^是异或操作，<<是左移，>>是右移
如果是一个有符号数，右移操作时，用符号位填补最左边的数字。
这道题问1的个数，考虑到只有1&1=1，所以可以将每一位与1做与操作，得到结果为1则表示该位位1 。这里需要考虑是将整数右移还是将1左移：整数右移需要考虑为负数时如何判断循环结束（整数为正数的话，右移左边补零，最后会为0），会造成死循环。而将1左移则可以避免这个问题。

代码实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        int flag = 1;
        while(flag != 0) {
            if((n & flag) != 0) {
                count++;
            }
            flag = flag << 1;
        }
        return count;
    }
}

解题思路二
考虑对一个整数做减法。假设这个整数的第m位是它从右边数的第一个1，即m右边都是0，减一之后，m位变成0，右边都是1 。而如果此时对n和n-1做与操作，会让从m位开始都为0了。或者说，每做一次这样的操作，n都会去掉一个1，直到变成全0 。

代码实现：

复制代码

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