题意:
提供一个无符号32位整型uint32_t变量n,返回其二进制形式的1的个数。
思路:
考察二进制的特性,设有k个1,则复杂度为O(k)。考虑将当前的数n和n-1做按位与,就会将n的最后一个1去掉,重复这样的操作就可以统计出1的个数了。(2015年春季 小米实习生的笔试题之一)
class Solution {
public:
int hammingWeight(uint32_t n) {
int cnt=;
while(n)
{
n&=n-;
cnt++;
}
return cnt;
}
};
AC代码
python3
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
cnt=0
while n:
cnt+=1
n=n&(n-1)
return cnt
AC代码