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:

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.

---

思路笔记

高效解

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

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

    public int findComplement(int num) {

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

    }

收获：与非位运算

我们首先要理解位运算：

说明：

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

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

非：

与：

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

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