Number of 1 Bits easy

Problem Statement

Write a function that takes an unsigned integer as input and returns the number of '1' bits (also known as the Hamming weight) in the binary representation of the integer.

Example 1

Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The binary representation of 11 is 1011, which has three '1' bits.

Example 2

Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The binary representation of 128 is 10000000, which has one '1' bit.

Steps

1. Convert the integer to its binary representation: While Python directly handles binary representation, we'll explicitly show the conversion for clarity.
2. Count the number of 1s: Iterate through the binary string and count the occurrences of '1'. Alternatively, we can use bit manipulation for a more efficient solution.

Explanation

The most straightforward approach involves converting the integer to its binary string representation and then counting the occurrences of '1'. However, a more efficient method uses bit manipulation. The & (bitwise AND) operator and right bit shift (>>) operator are particularly useful.

The bitwise AND operation (n & 1) checks if the least significant bit is 1. The right bit shift (n >> 1) shifts all bits to the right by one position, effectively discarding the least significant bit and moving the next bit into the least significant position. We repeat this process until all bits have been checked.

Code

def hammingWeight(n: int) -> int:
    """
    Counts the number of 1s in the binary representation of an integer.

    Args:
        n: An unsigned integer.

    Returns:
        The number of 1s in the binary representation of n.
    """

    # Method 1: Using bin() and count() (less efficient)
    # binary_representation = bin(n)[2:]  # [2:] removes "0b" prefix
    # count = binary_representation.count('1')
    # return count

    # Method 2: Using bit manipulation (more efficient)
    count = 0
    while n > 0:
        count += n & 1  # Check least significant bit
        n >>= 1         # Right bit shift
    return count

#Example Usage
n1 = 11
n2 = 128
print(f"Number of 1s in {bin(n1)}: {hammingWeight(n1)}") # Output: Number of 1s in 0b1011: 3
print(f"Number of 1s in {bin(n2)}: {hammingWeight(n2)}") # Output: Number of 1s in 0b10000000: 1

Complexity

• Time Complexity: O(log n) - The bit manipulation approach iterates through the bits of the integer, which is proportional to the number of bits (log₂n). The string conversion and counting method is also O(log n) but slightly less efficient due to string operations.
• Space Complexity: O(1) - The algorithm uses a constant amount of extra space regardless of the input size. The string conversion method uses O(log n) space in the worst case to store the binary string, but the bit manipulation method is more space-efficient.