Intuition

check if Least Significant bit is 1, if true increment count

Approach

• check if current Least Significant Bit is 1; if true increment bitCount by 1;
• Right shift the of n by 1 bit
• Repeat till n is 0

Complexity

• Time complexity: O(logn)
• reason, for a number \(x\) ; it would take \(log_2x\) bits to store the number.
• e.g \(64\) would take \(log_264\) i.e. \(6\) bits and we would thus iterate 6 times
• Space complexity: O(1)

Code

class Solution {
public:
    int hammingWeight(int n) {
        int bitCount = 0;
        int highestBit = 0;
        while(n){
            if( n & 1)
                bitCount++;
            n = n >> 1;    
        }
        return bitCount;
    }
};