首页 > 代码库 > [LeetCode] Number Complement 补数

[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: 5Output: 2Explanation: 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: 1Output: 0Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

 

这道题给了我们一个数,让我们求补数。通过分析题目汇总的例子,我们知道需要做的就是每个位翻转一下就行了,但是翻转的起始位置上从最高位的1开始的,前面的0是不能被翻转的,所以我们从高往低遍历,如果遇到第一个1了后,我们的flag就赋值为true,然后就可以进行翻转了,翻转的方法就是对应位异或一个1即可,参见代码如下:

 

解法一:

class Solution {public:    int findComplement(int num) {        bool start = false;        for (int i = 31; i >= 0; --i) {            if (num & (1 << i)) start = true;            if (start) num ^= (1 << i);        }        return num;    }};

 

由于位操作里面的取反符号~本身就可以翻转位,但是如果直接对num取反的话就是每一位都翻转了,而最高位1之前的0是不能翻转的,所以我们只要用一个mask来标记最高位1前面的所有0的位置,然后对mask取反后,与上对num取反的结果即可,参见代码如下:

 

解法二:

class Solution {public:    int findComplement(int num) {        int mask = INT_MAX;        while (mask & num) mask <<= 1;        return ~mask & ~num;    }};

 

再来看一种迭代的写法,一行搞定碉堡了,思路就是每次都右移一位,并根据最低位的值先进行翻转,如果当前值小于等于1了,就不用再调用递归函数了,参见代码如下:

 

解法三:

class Solution {public:    int findComplement(int num) {        return (1 - num % 2) + 2 * (num <= 1 ? 0 : findComplement(num / 2));    }};

 

参考资料:

https://discuss.leetcode.com/topic/74627/3-line-c

https://discuss.leetcode.com/topic/74968/simple-java-one-line-solution

https://discuss.leetcode.com/topic/74642/java-1-line-bit-manipulation-solution

 

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Number Complement 补数