【LeetCode】476.Number Complement 补数

﹏ヽ暗。殇╰゛Y 2022-06-01 02:08 123阅读 0赞

##### 题目 #####

题目地址 [https://leetcode.com/problems/number-complement/description/][https_leetcode.com_problems_number-complement_description]

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.

##### 思路 #####

1、很直白的一个思路就是 把整型数字转换为二进制形式，再将二进制数取反，但是要考虑到32位的二进制数除了将int目标数转换为二进制的低位  的左边的高位数上的0，因为这些0不能取反  不能作为结果计算进去；因此一开始我想到的是利用计算的方式（求余）得到对应二进制数再取反，最后得到结果。\[很直白=\_=所以效率也不高\]

这里需要明白list中index从低到高存的是 二进制从右到左 的数，因此不需要改顺序。

##### 我的代码   #####

#####  #####

##### （27ms） #####

public int findComplement(int num) {
            List<Integer> bit = new ArrayList<>();
            int res = 0;
            while(num !=0){
                bit.add(num%2);
                num /= 2;
            }
            //System.out.println("对应二进制："+bit);
            for(int i=0; i<bit.size(); i++){
                if(bit.get(i)==1) bit.set(i,0);
                else bit.set(i,1);
            }
            //System.out.println("取反后二进制："+bit);
            for(int i=0; i<bit.size(); i++){
                if(bit.get(i)==1){
                    res += (int)Math.pow(2,i);
                }
            }
            return res;
        }

#####  #####

##### 【讨论区答案1】 #####

##### **思路：** #####

1、目标数对应二进制取反，但仅在最左边（LEFTMOST）的1开始位到最右边，取反 **N**位。

eg，num=5 （二进制表示为101），LEFTMOST位为1是从RIGHTMOST开始数（100，N = 3）的第三个。然后我们需要从RIGHTMOST翻转 **3**位，答案是010。为了达到上述算法，我们需要做3个步骤：

**（1）**从最右边RIGHTMOST数创建一个N位为1的掩码。 在上面的例子中，掩码是111. 我们可以使用体面的Java内置函数Integer.highestOneBit来获得LEFTMOST位1 \[如上边的100\]，左移1，然后减1；

**（2）**目标数取反；

**（3）**将1和2的结果“&”运算。

\[目标数取反后高位也变成了1，掩码是高位为0 从LEFTMOST 1开始后边均为1，因此相与过滤掉高位1 得到目标结果。\]

##### **代码：（13ms）** #####

public int findComplement(int num) {
        return ~num & ((Integer.highestOneBit(num)<<1) - 1 );
    }

##### 【讨论区答案2】 #####

还有一个答案学习。

##### **原理**：（12ms） #####

##### 利用sum - 目标数 = 补数；如 num=5（101），利用（111）-（101）=（010）即2。 #####

public int findComplement(int num) {
        int i = 0;
        int j = 0;
        while (i < num)
        {
            i += Math.pow(2, j);
    	j++;
        }
        return i-num;
    }

**总结：**

1【技巧】  掩码如何求？  利用Integer.highestOneBit(num)函数得到LEFTMOST 1开始的后边所有位均为0的N位数，再左移<<1，再减1。

2 求幂 方法：Math.pow(2,i);

[https_leetcode.com_problems_number-complement_description]: https://leetcode.com/problems/number-complement/description/