题解 | 二进制中1的个数

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int NumberOf1(int n) {
        // write code here
        int cnt=0, t = 0;
        while(n!=0&&t<32){
            if(n&1) ++cnt;
            n = n>>1;
            ++t;
        }
        return cnt;
    }
};

位运算直接计1的数量，1往左移或者n往右移都行（保证了32位）。时间复杂度是O(1)（不保证位数是O(logn)），空间复杂度也是O(1)。

官网题解给出了和自己减去1的比较，很巧妙。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int NumberOf1(int n) {
        // write code here
        int res = 0;
        while(n){
            n &= n-1;
            ++res;
        }
        return res;
    }
};

减去1前面部分肯定不会改变，让最后面第一个有1的地方少1，也就是一次按位与少一个1。（后面变多的1前者也是没有的，按位与会消失）

时间复杂度是O(logn)，空间复杂度是O(1)。