BitOperation

发表于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/25/]

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

注意：

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

样例1

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

样例2

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

算法描述

经典题型，首先构造一个lowerbit(int x)函数，高效的位运算能迅速找到1的个数，特别是位数特别多的时候体现的，要做处理的是，输入的数为负数的时候需要转成对应的补码即(1<<31)+n即可；

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:

    int lowbit(int x){
        return x&(-x);
    }
    
    int NumberOf1(int n) {
        int ans = 0;
        if(n<0){
           n = (1<<31)+n;
           ans++;
        }
       
       while(n){
           n-=lowbit(n);
           ans++;
       }
       return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    
    public int lowbit(int x){
        return x&(-x);
    }
    
    public int NumberOf1(int n)
    {
        int ans=0;
        if(n<0){
            n=(1<<31)+n;
            ans++;
        }
        while(n!=0){
            n-=lowbit(n);
            ans++;
        }
        return ans;
    }
}