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

Explanation

For each bit \(i = 0, \dots, n - 1\), we retrieve the \(i`th bit (starting from least significant bit) and add 1 to the ``result`\) if it’s set. To check whether the \(i`th bit is set we can use ``(i << 1) & n`\) which creates a bit string that is 0 everywhere except at position \(i\) by bitshifting, then bitwise ands it with \(n\). The result is 0 if \(n\) is 1 at bit \(i\) or \(2^i\) otherwise.

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

Complexity

Measure	Complexity	Notes
Time	\(O(1)\)	integers only have 32 bits
Auxiliary Space	\(O(1)\)	no variables other than arguments, loop variable, and return value

number_of_1_bits__bit_scan.hammingWeight(n: int) → int

Return the number of set bits in n.

Brian Kernighan

Explanation

A faster solution is to count each 1 bit without having to go through 0 bits. Consider what happens to the binary represenation of \(n\) when we subtract 1. The lowest bit \(i\) of \(n\) becomes 0 while all other bits after \(i\) become 1. When we take the bitwise n & (n - 1), bits \(i\) (0 in \(n - 1\)) and \(i - 1, \dots, 0\) (0 in \(n\)) become 0. Thus n & (n - 1) clears the last bit of n. We repeat until \(n = 0\), with the number of iterations equaling the number of 1s in the binary representation of :math:`n.

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

Complexity

Measure	Complexity	Notes
Time	\(O(1)\)	integers can only have up to 32 1 bits
Auxiliary Space	\(O(1)\)	no variables other than arguments and return value

number_of_1_bits__brian_kernighan.hammingWeight(n: int) → int

Return the number of set bits in n.