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.我的解答：（找到第一个1，算法过于臃肿）
class Solution { public: int findComplement(int num) { bool meat1 = false; int flag = false; for(int i = 8 * sizeof(int) - 1; i >= 0 ; i--){ if(!meat1){ flag = num & (0x1 << i); } if(flag){ meat1 = true; } if(meat1){ num ^= (0x1 << i); } } return num; } }; Leetcode上看到的很快速的解法 class Solution { public: int findComplement(int num) { unsigned mask = ~0; while (num & mask) mask <<= 1; return ~mask & ~num; } };For example,
num = 00000101 mask = 11111000 ~mask & ~num = 00000010