Number of 1 Bits

Problem

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

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.

Constraints:

• 1 <= n <= 2³¹- 1

Pattern

Bit Manipulation

Approaches

Bit Scan

Code

def hammingWeight(n: int) -> int:
    """Return the number of set bits in *n*."""
    result = 0
    for i in range(32):
        if (1 << i) & n:
            result += 1
    return result

Test

>>> from number_of_1_bits__bit_scan import hammingWeight
>>> hammingWeight(11)
3
>>> hammingWeight(128)
1
>>> hammingWeight(2147483645)
30

number_of_1_bits__bit_scan.hammingWeight(n: int) → int

Return the number of set bits in n.

Brian Kernighan

Code

def hammingWeight(n: int) -> int:
    """Return the number of set bits in *n*."""
    result = 0
    while n > 0:
        n &= n - 1
        result += 1
    return result

Test

>>> from number_of_1_bits__brian_kernighan import hammingWeight
>>> hammingWeight(11)
3
>>> hammingWeight(128)
1
>>> hammingWeight(2147483645)
30

number_of_1_bits__brian_kernighan.hammingWeight(n: int) → int

Return the number of set bits in n.