[LeetCode] 476. Number Complement

https://leetcode.com/problems/number-complement/description/?envType=daily-question&envId=2024-08-22

leetcode - Number Complement

문제 유형 : 수학, 비트마스킹

문제 난이도 : Easy

 

문제

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 num, return its complement.

 

정수의 보수는 수의 이진 표현에서 1을 0으로, 0을 1로 변환한 것이다.

예를 들어, 101인 5의 보수는 010인 2이다.

 

정수 num이 주어지면, 보수를 구하시오.

 

풀이

숫자 num을 이진 표현할 때 필요한 비트 수는, log2(num) + 1이다.

그래서, (1 << (log2(num) + 1)) - 1을 해주면, 비트가 1로만 채워진 같은 비트의 수를 가진 수를 구할 수 있다.

이 수에다가 num을 xor연산시키면 된다.

 

예를 들어서, num = 5라고 해보자. 5는 이진 표현에서 101(2)이다.

log2(5) = 2.xxx이다.

소수 부분을 버리고 1을 더하면, 즉 올림처리 해주면 3이다.

1 << 3을 연산하면 1000(2). 즉 8이 된다.

1을 빼주면 7이 된다 (111(2)).

이렇게 같은 비트인데 1로만 채워진 수를 구해서 xor연산해주면, 보수를 구할 수 있다. 

111 xor 101 = 2.

 

INT_MAX와 같은 큰 값에 대비하여, 마스킹 할 수의 자료형을 확장해주자.

 

코드

C++

class Solution {
public:
    int findComplement(int num) {
        return num ^ (ulong(1 << ulong(log2(num)) + 1) -1);
    }
};