1009. Complement of Base 10 Integer

Problem

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 integer 2.

Given an integer n, return its complement.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: n = 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: n = 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Constraints:

• 0 <= n < 109

Problem Summary

Every non-negative integer N has its binary representation. For example, 5 can be represented in binary as "101", 11 can be represented in binary as "1011", and so on. Note that, except for N = 0, no binary representation contains leading zeros.

The binary complement is obtained by changing every 1 to 0 and every 0 to 1. For example, the binary complement of the binary number "101" is "010".

Given a decimal number N, return the decimal integer corresponding to the complement of its binary representation.

Solution Approach

• Easy problem. To find the complement of a decimal number, we only need to XOR the number with a number consisting entirely of 1s. Therefore, the key point of this problem is how to construct the mask.

Code

package leetcode

func bitwiseComplement(n int) int {
    mask := 1 
    for mask < n {
        mask = (mask << 1) + 1
    }
    return mask ^ n
}