# 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);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/476-number-complement.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.