Number of 1 Bits Python Solution with Tests

Tested Python solution for LeetCode 191 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 191, Easy. Topics: Divide and Conquer, Bit Manipulation. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 191   # by problem number
lcpy gen -s number_of_1_bits   # by problem name

​

Problem

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

​

Examples

Input: n = 11
Output: 3
Explanation:
The input binary string 1011 has a total of three set bits.

Input: n = 128
Output: 1
Explanation:
The input binary string 10000000 has a total of one set bit.

Input: n = 2147483645
Output: 30
Explanation:
The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

​

Constraints

• 1 <= n <= 2^31 - 1

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(1) - at most 32 iterations (number of bits in int)
    # Space: O(1) - only using constant extra space
    def hamming_weight(self, n: int) -> int:
        """
        Count the number of set bits (1s) in the binary representation of n.

        Uses the Brian Kernighan's algorithm:
        n & (n-1) removes the rightmost set bit from n.
        We keep doing this until n becomes 0, counting each iteration.

        This is more efficient than checking each bit individually
        because it only iterates for the number of set bits, not all bits.
        """
        count = 0
        while n:
            count += 1
            n &= n - 1  # Remove the rightmost set bit
        return count

​

Complexity

Time	Space
O(1) - at most 32 iterations (number of bits in int)	O(1) - only using constant extra space

​

Tags

Grind, Blind 75, NeetCode 150, NeetCode 250, NeetCode All.