Number of 1 Bits

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

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