Complement of Base 10 Integer - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
주어진 정수를 이진수로 표현했을 때 모든 0을 1로, 1을 0으로 바꿔서 얻을 수 있는 정수를 보수라고 한다.
- 예를 들어, 정수 5를 이진수로 나타내면 "101"이고 그 보수는 이진수 "010"으로 표현되는 정수 2이다.
정수 n이 주어졌을 때, 그 보수를 반환하시오.
조건
- 0 ≤ n < 1,000,000,000
해결
x = n + n'
n' = n - x
주어진 정수 n에 대하여 그 보수를 n'이라 해 봅시다.
그리고 고 두 수의 합 n + n' = x로 두었을 때, x를 이진수로 표현하면 다음과 같은 두가지 특징이 있습니다.
- 주어진 정수 n의 이진수 표현과 자릿수가 같다.
- 모든 비트가 1이다.
모든 비트가 1인 수 x는 쉽게 구할 수 있으므로, 여기서 n을 뺀 값을 구하면 보수 n'을 구할 수 있습니다.
코드
class Solution {
public:
int bitwiseComplement(int n) {
int x = 1;
while (n > x) x = x * 2 + 1;
return x - n;
}
};
TIL
C++ 비트 연산자 (Bitwise Complement)
C++에서 제공하는 비트 연산자(~) 중에서 보수 연산자도 존재합니다. 모든 비트를 뒤집는 역할을 하지만, 2의 보수를 반환하게 되므로 1의 보수를 구하는 위 문제에서는 직접적으로 활용하기가 어려웠습니다.
| 연산자 | 설명 |
| & | Bitwise AND |
| | | Bitwise OR |
| ^ | Bitwise XOR |
| ~ | Bitwise Complement |
| << | Bitwise Left Shift |
| >> | Bitwise Right Shift |
댓글