[LeetCode] 191. Number of 1 Bits

Problem : https://leetcode.com/problems/number-of-1-bits/

An one liner solution:

Time Complexity = O(1)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return sum([n >> offset & 1 for offset in range(32)])

Use bit manipulate trick to only count '1'

class Solution:
    def hammingWeight(self, n: int) -> int:
        result = 0
        while n:
            result += 1
            n = n & (n-1)
        
        return result

A divide and conquer approach. And use memorization to accelerate. ( The fastest solution. )

class Solution:
    def hammingWeight(self, n: int) -> int:
        
        #000 001 010 011 100 101 110 111
    
        @cache
        def helper(x):
            return helper(x >> 3) + helper(x & 7) if x > 7 else [0, 1, 1, 2, 1, 2, 2, 3][x]
                
        return helper(n)

Edited on 05/04/2021. Add the only count '1' solution.

Edited on 05/04/2021. Add the divide and conquer solution.