Number of 1 Bits

leetcode

C++ Solution

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n > 0) {
            if (n % 2 == 1) count++;
            n /= 2;
        }
        return count;
    }
};

the time complexity of this algorithm is O(log n) because we are dividing n by 2 in each iteration, which reduces the number of bits we need to check by half. The space complexity is O(1) since we are using only a constant amount of extra space to store the count variable.

a better solution Brian Kernighan's Algorithm

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // Removes the last '1' bit
            count++;
        }
        return count;
    }
};

n & (n - 1) is the key operation here. n - 1 set the LSB of n to 0, AND operation will remove all 0s in the number and only keep the 1s. So we can count how many times we can do this until n becomes 0, which will give us the number of 1s in the binary representation of n.

the time complexity of this algorithm is O(k), where k is the number of 1s in the binary representation of n. In the worst case, when n has all bits set to 1, the time complexity will be O(log n).