Number Complement

Link

Description

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

Example 1:

• Input: num = 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: num = 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.

Constraints:

• 1 <= num < 2^31

Solution

Way 1

class Solution {
public:
    int findComplement(int num) {
        int res = 0, t = 0;
        while (num) {
            res += !(num & 1) << t;
            num >>= 1;
            t++;
        }
        return res;
    }
};

• Time complexity: \(O(\log n)\);
• Space complexity: \(O(1)\).

Way 2

See reference (Chinese).

class Solution {
public:
    int findComplement(int num) {
        int x = 0;
        for (int i = num; i != 0; i -= i & -i) x = i;
        return ~num & (x - 1);
    }
};

Explanation:

Loop to Determine the Highest Bit Set in num:

for (int i = num; i != 0; i -= i & -i) x = i;

• This loop runs until i becomes 0.
• i -= i & -i: This operation is key. i & -i gives the lowest set bit in i. By subtracting this from i, we essentially turn off the rightmost set bit in every iteration.
• The loop continues until all bits are turned off, with x being assigned the value of i in each iteration. The final non-zero value of i (before becoming 0) is the highest set bit in num.

Complement Calculation:

return ~num & (x - 1);

• ~num: This operation flips all bits in num. If num is 5 (101 in binary), ~num will be ...11111010 in binary (in a 32-bit system, the leading bits are 1s because num is signed).
• (x - 1): This expression creates a bitmask. For example, if the highest set bit in num is the 3rd bit (like in 5, which is 101), x will be 100 in binary, and x - 1 will be 011.
• The & operation with x - 1 ensures that we only keep the relevant bits up to the highest bit set in num and discard the leading 1s introduced by the ~ operation.

Let's take an example to illustrate this:

Suppose num = 5 (101 in binary).

1. Highest Bit Calculation:
2. In the first iteration, i = 5 (101), and i & -i = 1 (001), so i becomes 4 (100).
3. In the next iteration, i = 4 (100), and i & -i = 4 (100), so i becomes 0.
4. The loop exits with x = 4 (100).
5. Complement Calculation:
6. ~num for 5 (000...000101 in binary) is 111...111010.
7. x - 1 is 3 (011 in binary).
8. The final result is 111...111010 & 000...000011, which equals 010 or 2 in decimal.

Therefore, the complement of 5 is 2.

Way 3

class Solution {
public:
    int findComplement(int num) {
        // if (!num) return 1;
        int cnt = 0;
        for (int x = num; x; x >>= 1) cnt++;
        return ~num & ((1LL << cnt) - 1);
    }
};