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;
     }
};

References

  1. 二进制中1的个数