LeetCode Number Complement Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation. Note:

1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
2. 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.

---

求一个数的二进制补，比如整数5的二进制是101，那么它的二进制补就是010，也就是整数2。求补的时候不能考虑前导零（leading zero）。 这个题好像AC率很高的，但是我还想了几天，之前的思路一直不对，我想的是判断到num中的一个0之后，ans就置1，然后往左移，但是这样的顺序和正确结果正好反了。 后来开窍了，num可以用移位的思想，但是ans可以不用移位，直接与上某个数，把对应位置1就好了。所以先要用一个变量i记录当前num已经移了多少位了，如果发现num当前位为0，则把ans中第i位置为1就好了，直到num为0。完整代码如下： [cpp] class Solution { public: int findComplement(int num) { int ans = 0, i = 0; while (num > 0) { if ((num & 1) == 0)ans |= (1 << i); num >>= 1; ++i; } return ans; } }; [/cpp] 本代码提交AC，用时3MS，居然只打败了5%的人，肯定还有其他方法。 网上找到这样一种解法。位运算的波浪号~本身就是取反操作，其实可以借用的。（我隐隐约约也感觉，这个位翻转的操作应该会有直接的位运算吧，可能是太久没用过~了，想不起来。） 但是~是对所有位进行翻转，包括翻转leading zero，所以需要对~稍加改造。~num翻转完之后，我们还要把leading zero翻回来，所以得知道哪些是leading zero。当num右移到0时，之前移过的肯定不是leading zero，所以之后的位肯定就是leading zero了，根据这个思路有下面的代码： [cpp] class Solution { public: int findComplement(int num) { int mask = 0xffffffff, tmp = num; while (tmp > 0) { mask <<= 1; tmp >>= 1; } return (~mask)&(~num); } }; [/cpp] 本代码提交AC，用时6MS，居然变慢了。。。不过多掌握一种思路也是好的。]]>