每个非负整数
N都有其二进制表示。例如，5可以被表示为二进制"101"，11可以用二进制"1011"表示，依此类推。注意，除N = 0外，任何二进制表示中都不含前导零。二进制的反码表示是将每个
1改为0且每个0变为1。例如，二进制数"101"的二进制反码为"010"。给定十进制数
N，返回其二进制表示的反码所对应的十进制整数。
示例 1：
输入：5 输出：2 解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。示例 2：
输入：7 输出：0 解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。示例 3：
输入：10 输出：5 解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
提示：
0 <= N < 10^9
解法一
//时间复杂度O(1), 空间复杂度O(1)
class Solution {
public:
int bitwiseComplement(int N) {
if(N == 0) return 1;
int temp = log2(N);//32位int，temp最大是30
int mask = (((1 << temp) - 1) << 1) + 1;
return ~N & mask;
}
};思路：
题目条上规定N是非负数（最高二进制位一定是1），我们第一步需要找到N的最高位的位置，令temp = log2(N)，这就是最高二进制位出现的位置（个位为第0位）。然后构造出一个蒙版mask，其中高于temp的位全为0，小于低于temp的位全为1。然后~N & mask就是我们要的答案。例如：
输入: N = 555 (二进制表示为 0010 0010 1011b)
计算 temp = log2(N) = log2(555) = 9
因为 1 << 9 = 0010 0000 0000b
(1 << 9) - 1 = 0001 1111 1111b
(((1 << 9) - 1) << 1 ) - 1 = 0011 1111 1111b
所以 mask = 0011 1111 1111b
~N = 1101 1101 0100b
~N & mask = 0001 1101 0100b = 468
返回: 468
2019/08/30 21:24