백준 / 수학 / 2089번 / -2진수 / C++

문제

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만

-2진법에서는 (-2)^0 = 1, (-2)^1 = -2, (-2)^2 = 4, (-2)^3 = -8을 표현한다.

10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

입력

첫 줄에 10진법으로 표현된 수 N이 주어진다.

출력

-2진법 수를 출력한다.

제한

• -2,000,000,000 ≤ N ≤ 2,000,000,000

예제 입력 1 

-13

예제 출력 1 

110111

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	string result;
	int n;
	cin >> n;
	
	if(!n) result = "0";
	else {
		while(n) {
			if(!(n % -2)) {
				result += "0";
				n /= -2;
			}
			else {
				result += "1";
				n = (n - 1) / -2;
			}
		}
	}
	
	reverse(result.begin(), result.end());
	cout << result << '\n';
		
	return 0;
}

---

10진수를 2진수로 나타내는 알고리즘이랑 비슷하지만 음수인거를 신경써줘야 한다.

이 문제는 알고리즘에 대한 사고력을 테스트하는 문제라기보단, 컴파일러가 음수연산을 어떻게 수행하는지 아는것이

중요한 문제인것 같다.

 

일단 양수일때와 음수일때를 나눠서 수를 몇가지 예시를 들어보겠다.

2진수 알고리즘을 나타낼땐 2로 계속나눈 나머지를 이어서 거꾸로 출력하면 되었다.

-2진수에서 예를들어, 4 / (-2) 는 딱 나누어지기 때문에 문제가 되지않는다.

하지만 홀수를 나눌경우, 그 중에서도 음수를 나눌경우 약간 다르다.

 

만약 5 / (-2)를 해야한다고 해보자.

그럼 우리는 이 연산을 (-2) * (-2) + 1 혹은 (-2) * (-3) - 1로 나타낼 수 있다.

만약 (-5) / (-2)는 어떨까?

음수도 두가지 케이스가 나온다.

(-2) * 2 - 1 혹은 (-2) * 3 + 1이 된다.

 

우리는 나머지로 진수를 표현하는데 음수값이 나오면 안된다.

그래서 만약 홀수일경우 미리 1을빼고 나눠준뒤 연산은 나누어 떨어지지만,

결과값에는 "1"을 += 해주면 정상적인 결과가 출력될것이다.