Description
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
Solutions
第一反应居然是循环的除以二,这样对于正数是可以做的,但是对于负数肯定就不好操作了。那么可以用位运算来做,向右位移以为就相当于除以2了。怎么判断是否是1呢?就让其结果跟1做与操作即可。当然这样还会有一个问题,那就是当输入是负数时会出现死循环的情况。那么采用一种取巧的做法,用无符号整型 1,一步一步左移一位来跟输入数据进行与操作,比较结果是否为1来判断是否有1.
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
# write code here
count = 0
flag = 1
while flag:
if n & flag:
count += 1
flag = flag << 1
return count
但是这个问题是,python 里没有无符号整型,于是还是会出现死循环的现象。所以要用 C++ 来实现:
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
unsigned int flag = 1;
while(flag){
if(flag & n){
count ++;
}
flag = flag << 1;
}
return count;
}
};
还有一种不需要其他辅助变量来做位运算的方法:
class Solution {
public:
int NumberOf1(int n) {
int count = 0;
while(n){
count ++;
n = (n-1) & n;
}
return count;
}
};