476. Number Complement的C++解法

本来以为上一道题我的写法是最蠢的，没想到这道题用了更蠢的写法，而且竟然没想出来怎么写效率更高。运行速度垫底。

class Solution { public: int findComplement(int num) { int x[32]; int i = 31; while (num) { x[i] = num % 2; num = num / 2; i = i - 1; } int k = i; int sum = 0; int l = 1; for (i = 31; i > k; i--) { if (x[i] == 0) sum = sum + l; l = l * 2; } return sum; } };

最优解思路：

仍然是按位操作取反即可，但是要想办法把前面的0过滤掉。使用掩码mask与原数做&运算找到前面所有多出来的0，将mask取反再与原数做&即可只保留不为0的部分。

最优解代码：

class Solution { public: int findComplement(int num) { unsigned mask = ~0; while (num & mask) mask <<= 1; return ~mask & ~num; } }; ~：按位取反，0在内存中的存储方式是所有位为0,即00000000。按位取反后为11111111（在机器中表示-1）。