> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/476-number-complement.md).

# 476 Number Complement

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

**Note:**

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. You could assume no leading zero bit in the integer’s binary representation.

**Example 1:**

```
Input:
 5

Output:
 2

Explanation:
 The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.
```

**Example 2:**

```
Input:
 1

Output:
 0

Explanation:
 The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.
```

**Complexity**: O(1) time, O(1) space

The Idea: First we find the first maximum significant bit. We do this by simply shifting 1 to the maximum bit location (30) (side note: 31 is reserved as the complement). Then we continue to shift this number to the right by 1 until it reaches the first 1. Then using `MAX_INT`, we can obtain all 1's and shift these to the right until we obtain the maximum significant digit that we found. Finally, `xor` 'ing this number with the result toggles everything.

```cpp
int getMostSignificantDigit(int num)
{
    int count = 0;
    int maxLeftPower2 = 1 << 30;

    while ((num & maxLeftPower2) == 0) {
        maxLeftPower2 >>= 1;
        count++;
    }
    return count;
}

int findComplement(int num) 
{
    int allOnesToMaxSigFig = INT_MAX >> getMostSignificantDigit(num);
    return num ^ allOnesToMaxSigFig;
}

int main()
{
    assert(findComplement(5) == 2);
    assert(findComplement(1) == 0);
    assert(findComplement(42) == 21);
}
```