leetcode-476

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:

1
2
3
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:

1
2
3
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.

这里的complement number是指二进制上的补，两个数的二进制加起来全是1（不包括前面的0）

用刚好比num大的二进制全是1的数-num就得到了complement number

这个解法比较易懂，但从运行时间上看不是最优解

1
2
3
4
5
6
7
8
9
10
11
12
int findComplement(int num)
{
    int sum = 0;
    int tmp = 1;
    while (sum < num)
    {
        sum += tmp;
        tmp = tmp << 1;
    }

    return sum - num;
}

看看LeetCode上其他版本的代码，主要的代码是拿到二进制中最左边那个1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findComplement(int num) {
        int toggled = num;

        int topBit = static_cast<int>(log2(num));  //得到num的最左边一个1的位置（把leading zero排除在外）
        for (int iBit = 0; iBit <=topBit; iBit++) {
            toggled ^= (1 << iBit); //（num的每一位和1做^操作取反）
        }

        return toggled;
    }
};