[C#] 1009. Complement of Base 10 Integer

 

1. 문제

 

정수의 보수란 이진 표현에서 모든 0을 1로, 1을 0으로 표현한 수이다.

 

예를 들면 정수 5는 2진 표현으로 101이고, 이의 보수는 정수 2인 010이다.

 

정수 n이 주어지면 보수를 반환하라.

 

 

---

 

2. 풀이 과정

 

간단하게 not 연산자를 쓰면 되는 거 아닌가? 했지만 int는 4byte니까 32개의 비트에 대해서 반전을 수행하므로 음수의 답이 나온다.

 

예를 들면 문제에서 5의 이진 표현은 101이라고 했지만 실은 0000 0000 0000 0000 0000 0000 0000 0101 이므로 NOT연산자를 사용하면

1111 1111 1111 1111 1111 1111 1111 1010 이 되므로 문제가 원하는 답이 아니다.

 

문제가 원하는 범위만큼만 반전시키기 위해 n의 2진법상 길이만큼의 filter를 만든 뒤 ~n과 filter를 AND연산하여 답을 출력하였다.

 

public class Solution {
    public int BitwiseComplement(int n) {
        if (n == 0)
            return 1;
            
        var reverse = ~n;
        var filter = 0;

        while(n > 0)
        {
            filter <<= 1;
            filter |= 1;
            n >>= 1;
        }

        return filter & reverse;
    }
}