二进制中1的个数

问题描述:

输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。

思路:

这个题目卡住我的原因就是我不知道怎么求补码了,其实负数在计算机中存储本来就是按照补码的形式,只是输出的时候又转化成我们对应的数.
另外这个题有一个比较基础的知识,也是比较容易陷入坑的一个点.对于c语言的移位运算符”<<”和”>>”对于无符号数他们都是直接补0即可;对于有符号数来说,左移运算还是按照逻辑左移一样直接补0,对于右移的话是在前面补符号位的,所以当n为负数的时候你直接每次右移来算是会死循环的!解决办法我们可以记录一下位数,最多32位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
int NumberOf1(int n) {
int cnt = 0;
int bit = 0;
while(bit <= 31)
{
if(n & 1) cnt++;
n >>= 1;
bit++;
}
return cnt;
}
};

还可以利用int向unsigned int 的转化,这里的转化是指:当一个负数向unsigned转化时会直接将其转化为一个补码。这时候就可以按照正数来进行正常的右移了.

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

还有一种更优化的方法就是: n = (n - 1) & n,这一步使得n中有多少个1就循环多少次,更优化。

class Solution {
public:
     int  NumberOf1(int n) {
        int cnt = 0;
        while(n)
        {
            cnt++;
            n = (n - 1) & n;
        }
        return cnt;
     }
};

-------------本文结束感谢您的阅读-------------

万水千山总是情,就给五毛行不行!

相关文章: