Solution 1 - Bit Shift and Count

Check each bit of n from right to left. Use n & 1 to check if the least significant bit is 1, increment the count if so, then right-shift n by one position. Repeat until n becomes 0.

TimeComplexity: O(32) = O(1)

SpaceComplexity: O(1)

""" 0191.1 - Number of 1 Bits - Solution 1 - Bit Shift and Count """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def hammingWeight(self, n: int) -> int:
        """Number of 1 Bits Function"""
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().hammingWeight(11))          # 3
    print(Solution().hammingWeight(128))         # 1
    print(Solution().hammingWeight(2147483645))  # 30


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brian Kernighan's Algorithm

Use the property that n & (n - 1) clears the rightmost set bit of n. Count how many times this operation can be performed until n becomes 0. This is more efficient when the number of set bits is small, as it only iterates once per set bit.

TimeComplexity: O(k), k = number of set bits

SpaceComplexity: O(1)

""" 0191.2 - Number of 1 Bits - Solution 2 - Brian Kernighan's Algorithm """

#####################################################################################
# Imports
#####################################################################################


#####################################################################################
# Classes
#####################################################################################
class Solution:
    """Solution Class"""

    def hammingWeight(self, n: int) -> int:
        """Number of 1 Bits Function"""
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    print(Solution().hammingWeight(11))          # 3
    print(Solution().hammingWeight(128))         # 1
    print(Solution().hammingWeight(2147483645))  # 30


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0191 - Number of 1 Bits

Solution 1 - Bit Shift and Count

Solution 2 - Brian Kernighan's Algorithm