# LeetCode 476: Number Complement

## Problem Restatement

We are given a positive integer `num`.

We need to flip every bit in its binary representation:

| Bit | After flip |
|---|---|
| `0` | `1` |
| `1` | `0` |

Then we return the decimal value of the flipped binary number.

For example, `5` in binary is:

```text
101
```

After flipping every bit:

```text
010
```

`010` in binary is `2`, so the answer is `2`.

The problem uses the normal binary representation without leading zeroes. This matters because we only flip the bits that are actually part of `num`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `num` |
| Output | The integer complement of `num` |
| Constraint | `1 <= num < 2^31` |

Function shape:

```python
def findComplement(num: int) -> int:
    ...
```

## Examples

Example 1:

```python
num = 5
```

Binary form:

```text
101
```

Flip every bit:

```text
010
```

Return:

```python
2
```

Example 2:

```python
num = 1
```

Binary form:

```text
1
```

Flip every bit:

```text
0
```

Return:

```python
0
```

## First Thought: Convert to String

A simple way is to convert the number to binary text.

For example:

```python
bin(5) == "0b101"
```

Then we can remove the `"0b"` prefix, flip each character, and convert the result back to an integer.

```python
class Solution:
    def findComplement(self, num: int) -> int:
        bits = bin(num)[2:]

        flipped = []
        for ch in bits:
            if ch == "0":
                flipped.append("1")
            else:
                flipped.append("0")

        return int("".join(flipped), 2)
```

This works, and it is easy to understand.

## Problem With the String Method

The string method depends on converting between integer and text.

That is fine for this problem, but the problem is really about bits. A direct bit manipulation solution is shorter and closer to the idea.

We want to flip only the meaningful bits of `num`.

For `num = 5`, the meaningful bits are:

```text
101
```

We do not want to think of it as a 32-bit integer like this:

```text
00000000000000000000000000000101
```

If we directly use `~num`, Python gives a negative result because Python integers use signed arithmetic behavior for bitwise complement.

So we need a mask.

## Key Insight

To flip exactly the bits of `num`, build a mask with the same number of bits, all set to `1`.

For `num = 5`:

```text
num  = 101
mask = 111
```

Now XOR flips every bit where the mask has `1`.

```text
101
111
---
010
```

So:

```python
5 ^ 7 == 2
```

The mask for a number with `k` bits is:

```python
(1 << k) - 1
```

For `num = 5`, `k = 3`.

```python
1 << 3 == 8      # binary 1000
8 - 1 == 7       # binary 0111
```

So the mask is `7`, or `111` in binary.

## Algorithm

First, find how many bits are needed to represent `num`.

Python gives this directly:

```python
k = num.bit_length()
```

Then build the mask:

```python
mask = (1 << k) - 1
```

Then flip the bits by XOR:

```python
answer = num ^ mask
```

Return `answer`.

## Correctness

Let `k` be the number of bits in the binary representation of `num`.

The mask:

```python
(1 << k) - 1
```

has exactly `k` bits, and every one of those bits is `1`.

For every bit position used by `num`, XOR with `1` flips the bit:

| Original bit | Mask bit | XOR result |
|---|---|---|
| `0` | `1` | `1` |
| `1` | `1` | `0` |

Therefore, `num ^ mask` flips every bit in the binary representation of `num`.

The mask has no extra `1` bits beyond the length of `num`, so no leading positions are changed.

Thus the algorithm returns exactly the complement required by the problem.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | `num < 2^31`, so there are at most 31 bits |
| Space | `O(1)` | Only a few integer variables are used |

If we write the complexity in terms of the number of bits `k`, the time is `O(k)` for computing bit length and bit operations. Under the given constraint, `k <= 31`, so it is constant.

## Implementation

```python
class Solution:
    def findComplement(self, num: int) -> int:
        k = num.bit_length()
        mask = (1 << k) - 1
        return num ^ mask
```

## Code Explanation

This line gets the number of meaningful bits:

```python
k = num.bit_length()
```

For example:

| `num` | Binary | `bit_length()` |
|---|---|---|
| `1` | `1` | `1` |
| `5` | `101` | `3` |
| `10` | `1010` | `4` |

This line creates a mask of `k` ones:

```python
mask = (1 << k) - 1
```

For `k = 4`:

```text
1 << 4 = 10000
10000 - 1 = 01111
```

Then this line flips all meaningful bits:

```python
return num ^ mask
```

For `num = 10`:

```text
num  = 1010
mask = 1111
xor  = 0101
```

So the answer is `5`.

## Testing

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

    assert s.findComplement(5) == 2
    assert s.findComplement(1) == 0
    assert s.findComplement(10) == 5
    assert s.findComplement(7) == 0
    assert s.findComplement(8) == 7

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `5 -> 2` | Main example: `101 -> 010` |
| `1 -> 0` | Smallest valid input |
| `10 -> 5` | Alternating bits: `1010 -> 0101` |
| `7 -> 0` | All bits are `1`: `111 -> 000` |
| `8 -> 7` | Power of two: `1000 -> 0111` |