Number Complement

May 4, 2020

Introduction

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its 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.

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.
This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

Solution

We know that operator xor reverts bits, basically complements the integer with ones. All we need is to find meaning ones, to skip zeros. In this case mask works the best. We put in mask bits that will participate in xor operation.

func findComplement(num int) int {
    mask := 0
    for v := num; v > 0; v >>=1 {
        mask <<= 1
        mask |= 1
    }
    return num ^ mask
}