191.Number_of_1_bits_(Easy).md

191. Number of 1 Bits (Easy)

Date and Time: Jul 1, 2024, 18:30 (EST)

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

Question:

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:
The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:
The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

KeyPoints:

Mod 2 to get the reminder if the remainder is 1, it is the set bit, then logical right shift by 1 and repeat.

The below two solutions are doing the same thing, but the first solution shift bit right by 1 bit, which has the same effect as half a number (ie. 10 -> 5).

My Solution:

class Solution:
    def hammingWeight(self, n: int) -> int:
        # 11 -> 1011, 1011 % 2 = 505 R 1
        res = 0
        while n:
            if n % 2 == 1:
                res += 1
            n = n >> 1
        return res

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Alternative Solution:

The intuition is when n = 11, n % 2 = 1, then we update n = n // 2 = 5, repeat that n % 2 = 1, n = 5 // 2 = 2; n % 2 = 0, n = n // 2 = 1; 1 % 2 = 1, n = 1 // 2 = 0.

class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n != 0:
            if n % 2 == 1:
                res += 1
            n = n // 2
        return res