# LeetCode 191: Number of 1 Bits

## Problem Restatement

We are given a positive integer `n`.

We need to return the number of `1` bits in its binary representation. This count is also called the Hamming weight. The official problem asks for the number of set bits in the binary representation of `n`.

A set bit means a bit whose value is `1`.

For example:

```text
n = 11
binary = 1011
```

There are three `1` bits, so the answer is:

```python
3
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | Number of `1` bits in the binary representation |
| Name | Hamming weight |
| Main operation | Bit counting |

Example function shape:

```python
def hammingWeight(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 11
```

Binary:

```text
1011
```

The `1` bits are:

```text
1 0 1 1
^   ^ ^
```

There are `3` set bits.

Output:

```python
3
```

Example 2:

```python
n = 128
```

Binary:

```text
10000000
```

There is only one `1` bit.

Output:

```python
1
```

Example 3:

```python
n = 2147483645
```

This number has `30` set bits.

Output:

```python
30
```

## First Thought: Check Every Bit

A simple way is to repeatedly check the last bit.

The expression:

```python
n & 1
```

returns `1` if the last bit is `1`, otherwise it returns `0`.

Then we shift `n` right by one bit:

```python
n >>= 1
```

This removes the last bit and moves the next bit into place.

That approach works.

```python
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n:
            count += n & 1
            n >>= 1

        return count
```

This checks every bit position until `n` becomes zero.

## Key Insight

There is a faster bit trick.

The expression:

```python
n & (n - 1)
```

removes the rightmost `1` bit from `n`.

Example:

```text
n       = 1100
n - 1   = 1011
n&(n-1) = 1000
```

The rightmost `1` in `1100` was removed.

So instead of checking every bit, we can remove one set bit at a time and count how many removals happen.

For example:

```text
n = 1011
```

First removal:

```text
1011 & 1010 = 1010
```

Second removal:

```text
1010 & 1001 = 1000
```

Third removal:

```text
1000 & 0111 = 0000
```

We removed three `1` bits, so the answer is `3`.

## Algorithm

1. Set `count = 0`.
2. While `n` is not zero:
   - Replace `n` with `n & (n - 1)`.
   - Increase `count` by `1`.
3. Return `count`.

Each loop removes exactly one set bit.

## Correctness

At every iteration, `n & (n - 1)` removes the lowest set bit of `n`.

So each iteration reduces the number of `1` bits by exactly one.

The loop stops when `n` becomes zero.

A number is zero exactly when it has no `1` bits left.

Therefore, the number of iterations is exactly the number of original set bits in `n`.

Since `count` increases once per removed set bit, the final `count` equals the Hamming weight of the original number.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(b)` | The loop runs once per set bit |
| Space | `O(1)` | Only a counter is stored |

Here, `b` is the number of `1` bits in `n`.

For a 32-bit integer, this is also `O(1)` because there are at most `32` bits.

## Implementation

```python
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n:
            n &= n - 1
            count += 1

        return count
```

## Code Explanation

We start with zero counted bits:

```python
count = 0
```

The loop continues while some set bit still exists:

```python
while n:
```

This line removes the rightmost set bit:

```python
n &= n - 1
```

After removing one set bit, we count it:

```python
count += 1
```

When `n` becomes zero, all set bits have been removed, so we return:

```python
return count
```

## Alternative Implementation: Fixed 32-Bit Scan

This version checks all 32 bit positions.

```python
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        for _ in range(32):
            count += n & 1
            n >>= 1

        return count
```

This is also valid for a 32-bit input. It always performs exactly 32 iterations.

The `n & (n - 1)` version can use fewer iterations when the number has only a few set bits.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.hammingWeight(11) == 3
    assert s.hammingWeight(128) == 1
    assert s.hammingWeight(2147483645) == 30
    assert s.hammingWeight(1) == 1
    assert s.hammingWeight(0) == 0
    assert s.hammingWeight(15) == 4

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `11` | Binary `1011`, main small example |
| `128` | Single set bit |
| `2147483645` | Large input with many set bits |
| `1` | Smallest positive set bit case |
| `0` | No set bits |
| `15` | Binary `1111`, all low bits set |