leetcode解题: Number Complement (476)

发表于 | 分类于

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

Note:
The given integer is guaranteed to fit within the range of a 32-bit signed integer.
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
Input: 1
Output: 0

解法1：

观察可以发现，可以用XOR来flip每一位的bit， 而mark数是从第一个set bit开始所有位都为1的数字。
怎么判断最高的set bit是哪一个呢？可以用log2函数，最高位的1的位置一定是log2(num), 那么为了得到所有都是1的一个数，可以先左移log2(num) + 1， 然后把所得的数字-1即可。
C++

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int findComplement(int num) {
        int mask = (1 << 1 + static_cast<int>(log2(num))) - 1;
        return mask ^ num;
    }
};

Java

1
2
3
4
5
6
7
8
class Solution {
    public int findComplement(int num) {
        int mask = (1 << ((int)(Math.log10(num) / Math.log10(2)) + 1)) - 1;
        return num ^ mask;
    }
}

解法2：一位一位的转换

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findComplement(int num) {
    // last digit is set bit
    int pos = 0;
    int res = 0;
    for (int i = 0; i < 31 && num != 0; i++) {
        int digit = num & 1;
        num >>= 1;
        pos++;
        int setBit = 1 - digit;
        setBit <<= i;
        res |= setBit;
    }
    return res;
}