476. Number Complement

Problem

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.

Problem Summary

Given a positive integer, output its complement. The complement is obtained by flipping the binary representation of the number.

Note:

The given integer is guaranteed to be within the range of a 32-bit signed integer. You can assume that the binary number does not contain leading zero bits.

Solution Approach

To find the complement of a positive number, the definition of the complement is to flip the binary representation of the number. The sign bit cannot be changed. Construct the corresponding mask according to the problem statement and then invert it.

Code


package leetcode

// Solution 1
func findComplement(num int) int {
	xx := ^0 // ^0 = 1111111111111111111111
	for xx&num > 0 {
		xx <<= 1 // The constructed xx = 1111111…000000, the number of 0s is the length of num
	}
	return ^xx ^ num // xx ^ num, the result is num with all leading 0s turned into 1s, then invert it to get the answer
}

// Solution 2
func findComplement1(num int) int {
	temp := 1
	for temp <= num {
		temp <<= 1 // The constructed temp = 00000……10000, the number of trailing 0s is the length of num
	}
	return (temp - 1) ^ num // temp - 1 is the number with leading bits all 0 and trailing bits of num's length all 1s; XOR it with num to get the final result
}