10진수 정수 변환
Algorithm 1.
1. 주어진 10진수 값을 2로 나누고 그 나머지를 기록한다.
2. 몫이 0이 아니면 새로운 몫을 2로 나누고 그 나머지는 기록한다.
3. 몫이 0이면 나머지가 기록되는 순서대로 왼쪽에서 오른쪽으로 나열한다.
4. 나열한 숫자가 주어진 값의 2진수 표현이다.
Proof. 주어진 10진수 값을 $x$라고 하면 $x$는 Division Algorithm에 의해 다음과 같이 쓸 수 있다. $$x = 2 \cdot Q_1 + R_1 (0 \leq R_1 < 2)$$ 동일하게 $Q_1$에 대해서도 위와 같이 작성하면 $$x = 2 \cdot (2 \cdot Q_2 + R_2) + R_1 (0 \leq R_1, R_2 < 2)$$이고, 이와 같은 과정을 반복하면 자연수 $N$에 대해 아래와 같이 쓸 수 있다. $$x = 2 \cdot (2 \cdot ( \cdots \cdot (2 \cdot (2 \cdot 1 + R_N) + R_{N-1}) \cdots )) \\ = 1 \cdot 2^N + R_N \cdot 2^{N-1} + R_{N-1} \cdot 2^{N-2} + \cdots + R_2 \cdot 2^1 + R_1 \cdot 2^0 = (1 R_N R_{N-1} \cdots R_2 R_1)_2 \blacksquare$$
10진수 소수 변환
Algorithm 2.
1. 주어진 10진수 소수의 정수 부분이 0이 아니라면 정수 부분과 소수 부분으로 구분하고, 정수 부분은 Algorithm 1을 이용하여 2진수로 변환해준다. 정수 부분이 0이라면 2번으로 넘어간다.
2. 주어진 10진수 소수 부분에 2를 곱한 값에 정수 부분은 따로 분리하여 오른쪽에서 왼쪽으로 적고, 소수 부분이 0이 아니라면 소수 부분을 새로운 10진수 소수로 취급하여 1번을 반복한다.
3. 소수 부분이 0이라면 반복을 멈춘다.
4. 적어준 정수 부분 앞에 0과 소수점을 붙혀서 얻은 값이 주어진 값의 2진수 표현이다.
Proof. 주어진 10진수 소수를 $x$라 하자. 이때 $x$의 2진수 표현 $x_2$는 어떤 자연수 $N$에 대해 다음과 같이 쓸 수 있다. $$x_2 = a_1 \cdot 2^{-1} + a_2 \cdot 2^{-2} + \cdots + a_N \cdot 2^{-N}$$ 위 알고리즘의 방법과 같이 2를 계속 곱해 나열하면 다음과 같다. $$a_1 + a_2 \cdot 2^{-1} + \cdots + a_N \cdot 2^{-N+1} \\ a_2 + a_3 \cdot 2^{-1} + a_N \cdot 2^{-N+2} \\ \vdots \\ a_N \\ \Longrightarrow x_2 = 0.(a_1 a_2 \cdots a_N)_2 \blacksquare$$