Leetcode: 191. Number of 1 Bits

Problem Statement

Pattern

Solution

Given an integer \(n\), the task is to find the number of 1 bits in \(n\). If \(n=0\), the answer is clearly \(0\). Otherwise, the answer is the sum of \(n \mod 2\) and the number of 1 bits in \(\lfloor \frac{n}{2} \rfloor\). The following algorithm implements this process iteratively using logical operators. The time complexity is constant since the loop executes at most 32 times. 

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

Cited by 2