We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of 1 Bits

Number: 191

Difficulty: Easy

Paid? No

Companies: Google, Box, Apple, Amazon, Meta, Microsoft, Adobe, Nvidia, AMD

Problem Description

Given a positive integer n, determine the number of set bits (1s) in its binary representation. This count is also known as the Hamming weight of the number.

Key Insights

  • The problem is essentially counting the number of 1s in the binary representation of a number.
  • A common efficient approach uses bit manipulation: repeatedly clear the lowest set bit until n becomes zero.
  • The expression n & (n - 1) clears the lowest set bit of n.
  • This method only iterates as many times as there are set bits, making it efficient.

Space and Time Complexity

Time Complexity: O(k), where k is the number of set bits, worst-case O(log n) (or O(1) considering 32-bit integers).
Space Complexity: O(1).

Solution

To solve the problem, we use the bit manipulation trick n & (n - 1) which removes the lowest set bit from n. The algorithm is as follows:

  1. Initialize a counter to 0.
  2. While n is not zero, update n by n = n & (n - 1), and increment the counter.
  3. The counter will hold the number of set bits by the end of the loop. This approach leverages efficient bit-level operations and works well even when the function is called frequently.

Code Solutions

# Function to count the number of set bits in a given integer n
def hammingWeight(n: int) -> int:
    count = 0  # Initialize count of set bits
    while n:
        # Remove the lowest set bit from n
        n &= n - 1  
        count += 1  # Increment count for each set bit removed
    return count

# Example usage:
print(hammingWeight(11))  # Output: 3
← Back to All Questions