476. Number Complement
Description
The complement of an integer is the integer you get when you flip all the 0
's to 1
's and all the 1
's to 0
's in its binary representation.
- For example, The integer
5
is"101"
in binary and its complement is"010"
which is the integer2
.
Given an integer num
, return its complement.
Example 1:
Input: num = 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: num = 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.
Constraints:
1 <= num < 231
Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/
Solutions
Solution 1: Bit Manipulation
According to the problem description, we can use XOR operation to implement the flipping operation, the steps are as follows:
First, we find the highest bit of $1$ in the binary representation of $\textit{num}$, and the position is denoted as $k$.
Then, we construct a binary number, where the $k$-th bit is $0$ and the rest of the lower bits are $1$, which is $2^k - 1$;
Finally, we perform XOR operation on $\textit{num}$ and the constructed binary number to get the answer.
The time complexity is $O(\log \textit{num})$, where $\textit{num}$ is the input integer. The space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 |
|
1 2 3 4 5 6 7 |
|
Solution 2: Bit Manipulation. Inversion + AND
1 2 3 |
|
1 2 3 4 5 6 7 |
|