Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0191 - Number of 1 Bits
    0191 - Number of 1 Bits
    0191 - Number of 1 Bits
    0191 - Number of 1 Bits

    0191 - Number of 1 Bits

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/number-of-1-bits/

    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)TimeComplexity: O(32) = O(1)TimeComplexity:O(32)=O(1)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)

    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=numberofsetbitsTimeComplexity: O(k), k = number of set bitsTimeComplexity:O(k),k=numberofsetbits
    SpaceComplexity:O(1)SpaceComplexity: 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()

    """ 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()