476-数字的补数

LeetCode 476. Number Complement

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.

method

只需要取反表示数值的Bit，前面的0不动，比如0000 1101要转为0000 0010，而不是1111 0010

某个数num的最高位1在i位，则其范围为$2^i \leq num < 2^{i+1}$，通过比较就可以找到最高位1的位置，然后将i位及其后面的位取反，当然这里没办法取反，只能用与1相异或，~1011 = 0100 等价于1011 ^ 1111 = 0100，而构造第i位之后全为1的数可以用$2^{i+1}-1$，例如i=4，$2^4-1=15=1111$

当i=30时要特判，因为$2^{31}=-2147483648$，再减1就溢出了，所以就直接输入其掩码，最高位为0，其他全为1的数0x7f ff ff ff，也就是INT_MAX

int findComplement(int num) {
    int high = 0;   // 找到第一个1
    for (int i = 1; i <= 30; i++) {
        if (num >= (1 << i)) high = i;
        else break;
    }
    int mask = 0;
    if (high == 30) mask = 0x7fffffff;
    else mask = (1 << (high + 1)) - 1;
    return num ^ mask;
}