> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/bit-manipulation/binary-bits-count.md).

# Binary Bits Count

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has.

```
Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
 


```

#### Constraints:

The input must be a binary string of length `32`.

### Solution 1

```C#
public int CountBits(uint n) {
    int count = 0;
    while (n != 0) {
        count += (int)(n & 1);
        n >>= 1;
    }
    return count;
}

```

This function works by iterating through the bits of `n` from right to left. In each iteration, it adds the least significant bit of `n` to `count`, and then shifts `n` to the right to process the next bit. This continues until all bits of `n` have been processed.

The time complexity of the algorithm is **O(log(n))**, where n is the input to the function. This is because in each iteration of the while loop, we’re dividing n by 2, effectively reducing the problem size by a factor of 2. Hence, the number of iterations is proportional to the number of bits in n, which is log(n) in base 2.

The space complexity of the algorithm is **O(1)**, which means it uses a constant amount of space. This is because we’re only using a fixed number of variables and not any data structures that grow with the size of the input. The integer count and the input n are the only variables being used, and their size does not change with different inputs.

### Solution 2

```csharp
public int CountBits(uint n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

```

In this algorithm, the expression `n & (n - 1)` removes the least significant ‘1’ bit from `n`. This is repeated until `n` becomes `0`, and the number of iterations is equal to the number of ‘1’ bits in `n`.

The time complexity of this algorithm is **O(k)**, where k is the number of ‘1’ bits in n. This is because each iteration of the loop eliminates one ‘1’ bit. In the worst case, when `n` is a power of `2`, the time complexity is **O(log(n))**, which is the same as your first algorithm. However, on average, this algorithm will be faster if `n` has relatively few ‘1’ bits.

The space complexity remains **O(1)**, as we’re only using a fixed number of variables.