number-of-1-bits

Number of 1 Bits – LeetCode 191

Problem

Description

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

Answer

Original

Code

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned r = 0;
        for(unsigned i = 0; i != 32; ++i, n >>= 1){
            r += n & 0x1;
        }
        return r;
    }
};

思路

简单的移到尾部然后叠加。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$77.41\%$

Better

思路

对于n & (n - 1)的使用，可以令末尾的1变成0，只需要循环r次，有性能优化,时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$3$ ms，排名$88.57\%$

Code

class Solution {
public:
    int hammingWeight(uint32_t n) {
        unsigned r = 0;
        while (n >0) {
            r++;
            n &= (n-1);
        }
        return r;
    }
};