LeetCode_Easy_471:Number Complement

题目描述

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.

思路笔记

高效解

我能想到的直观思路，就是在二进制转十进制的时候将各位余数数值取反，然后再转换为十进制。

但是知道我看到了最优解：Java 1 line bit manipulation solution(仅仅一句话代码)

    public int findComplement(int num) {

        return ~num & ((Integer.highestOneBit(num) << 1) - 1);

    }

收获：与非位运算

我们首先要理解位运算：

说明：

位运算包括：“与”、“非”、“或”、“异或”。

运算符主要针对两个二进制数的位进行逻辑运算。

非：

非运算符用符号“~”表示，其运算规律如下：

如果位为0，结果是1，如果位为1，结果是0，也就是每位都取反了。
public static void main(String[] args)

{

   int a=2;

   System.out.println("a 非的结果是："+(~a));

}
在上述代码中：结果是 10 —> 01

与：

与运算符用符号“&”表示，其使用规律如下：

两个操作数中位都为1，结果才为1，否则结果为0
public static void main(String[] args)

{

  int a=129;

  int b=128;

  System.out.println("a 和b 与的结果是："+(a&b));

}
在上述代码中：结果是 100101001&100101000—>100101000

然后我们总结一下一句话代码：

假设Num=5(101),我们求出其非值为(11111111111111111111111111111010)这是一个32位的值，可是我们只想要其后三位。
Integer.highestOneBit(num) << 1) - 1，可以快速求出和其长度相同的且各位为1的值，即111。
两者求与，剩下的就是010。

巴特西

LeetCode_Easy_471:Number Complement

LeetCode_Easy_471:Number Complement

题目描述

思路笔记

高效解

收获：与非位运算

最新文章

热门文章