Number of 1 Bits

Updated on 03 July, 2025
Number of 1 Bits header image

Problem Statement

In this task, you are provided with a positive integer n. The objective is to design a function that calculates and returns the number of set bits (1-bits) in the binary representation of the number. This calculation is generally referred to as finding the Hamming weight of the number. Determining the Hamming weight involves counting how many bits in a number's binary form are '1'.

Examples

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 <= 231 - 1

Approach and Intuition

The task revolves around counting the bits set to '1' in a binary representation. Here's how you can approach this problem based on the provided examples:

  1. Convert the given integer n to its binary form. This can be done using built-in methods or manual bit manipulation.
  2. Count the number of '1's in that binary representation.
  • Example Walkthroughs:
    • For n = 11, the binary form is 1011. Counting the '1's gives us three, which is the output.
    • In the case of n = 128, the binary representation is 10000000. This contains only one '1', leading to an output of 1.
    • For n = 2147483645, the number's binary equivalent is extensively filled with '1's except for the last bit, totaling up to thirty set bits.

From the explanation and examples, it's clear that the method is straightforward. There's a direct relationship between the binary representation's set bits and the task's output. You would loop over the string or manipulate the number directly to count the '1's, adhering to the constraint 1 <= n <= 231 - 1. This ensures we cover all valid 32-bit integers, considering the problem's limiting values.

Solutions

  • Java
java
public int countOnes(int num) {
    int count = 0;
    while (num != 0) {
        count++;
        num &= (num - 1);
    }
    return count;
}

In this solution, you write a method to count the number of '1' bits (set bits) in an integer's binary representation. The method countOnes(int num) initializes a counter count to zero. It then enters a while loop that continues as long as num is not zero. At each iteration of the loop, count is incremented and num is updated to num AND (num - 1). This operation clears the lowest set bit of num, progressively reducing it to zero. The method returns the count, effectively giving the number of '1' bits in the original integer.

  • Key aspects of this approach:
    • Utilizes bit manipulation to clear the lowest set bit, which is very efficient.
    • Operates directly on the binary form of the given integer.
    • The time complexity is proportional to the number of '1' bits in num, making it optimal for sparse bit sets.

Comments

No comments yet.