原题链接
https://leetcode.com/problems/number-complement/
原题
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:
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.
题目要求
题目要求为：给定一个非负整数，求出其complement number。所谓complement number，指对整数二进制最高位为1的位之后的所有位置取反，如5的二进制表示为00……00101，起最高位为1的位置是3，因此只对3之后的所有位置取反，得到00*00010，最后得出complement number为2。
解法
解法一：先求出最高位为1的位数，然后计算出掩码，再将原数据取反后和掩码求与，即得出最后结果。
public int findComplement(int num) {
int valid = 0; // 最高位为1的位数
int tmp = num;
while(tmp > 0) {
tmp /= 2;
valid++;
}
return ~num & ((1 << valid) - 1);
}
其中，(1 << valid) - 1是二进制操作中一种常用的求掩码的方式，如valid为3，那么1<<valid二进制为1000，再减去1就得到了0000111。
Top解法：Top解法与解法一完全一致，只是使用了Java库实现的求出最高位为1的库函数而已。当然，代码更加简洁。
public int findComplement(int num) {
return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}
测试用例：
public static void main(String[] args) {
Solution s = new Solution();
assert(s.findComplement(5) == 2);
assert(s.findComplement(1) == 0);
assert(s.findComplement(0) == 0);
}