[leetcode #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 < 10⁹

Idea

Complement를 구하는 기초 중의 기초는 mask를 구하는 것이다. mask는 XOR 연산을 위해 해당 수의 bit 수가 전부 1인 수를 말한다. mask만 구하면 XOR 연산을 통해 바로 답을 구할 수 있다.

mask를 구하기 위해 주어진 수를 2로 나눈 뒤 나눈 횟수를 bit 수로 정했다. 이 때 구한 bit 수만큼 1을 left 한 뒤 1을 빼면 mask가 나온다.

mask와 n을 XOR 연산하면 complement 값이 구해진다.

더 간단한 방법은 mask를 비교하는 것이다. mask는 1부터 시작한다. n이 mask 값보다 작을 때까지 mask에 2를 곱한 뒤 1을 더한다. 이후 mask에서 n을 빼면 complement를 구할 수 있다.

Solution

class Solution {
    public int bitwiseComplement(int n) {
        if (n == 0) {
            return 1;
        }

        int dividend = n;
        int binaryLen = 0;

        while (dividend != 0) {
            binaryLen++;
            dividend /= 2;
        }

        int mask = 1;
        for (int i=0; i < binaryLen; i++) {
            mask = mask << 1;
        }
        mask -= 1;

        return (mask ^ n);
    }
}

훨씬 쉽게 푸는 법은 다음과 같다.

class Solution {
    public int bitwiseComplement(int n) {
        int x = 1;

        while (n > x) {
            x = (x << 1) + 1;
        }

        return x - n;
    }
}

Reference

https://leetcode.com/problems/complement-of-base-10-integer/