10진법을 2진법으로 변환

진법(進法)

10진법은 1,2,3,…9까지 하나씩 증가하다가 하나 더 증가하면 10이 되는것이고, 2진법은 숫자를 하나씩 증가하다가 2가되면 10(2)이 되는것이다. 즉, 진법
(進法)이라는것은 숫자가 하나씩 증가하다가 맥시멈(2혹은 10)이 되면 자리수가 나아가는(進) 개수의 표현 방법(法) 이다.

직관적인 방식으로 변환하기

5라는 숫자는 1 -> 2 -> 3 -> 4 -> 5 라는 과정을 거쳐서 5가 된것이다. 2진법으로 표현하면, 1 -> 10 -> 11 -> 100 -> 101(2)이 된것이다. 변환 과정은 쉽다. 일단 맨 오른쪽에 1을 더하고 해당 자리의 숫자가 2가 되면 0으로 바꾸고 그 왼쪽에 1을 더하거나 없다면 추가한다. 근데 그것도 2가 되면 또 0으로 바꾸고 왼쪽에 1을 더하거나 추가한다. JS코드는 아래와 같다.

result를 받아서 거꾸로 출력해주면 된다.

규칙성이 보인다

10진수를 2진수로 변환하다 보면 규칙성이 보인다.

10 = 8 + 2 = 23 + 21 = 1010(2)

15 = 8 + 4 + 2 + 1 = 23 + 22 + 21 + 1 = 1111(2)

16 = 24 = 10000(2)

22 = 16 + 4 + 2 = 24 + 22 + 21 = 10110(2)

왼쪽 부터 큰 순서대로 2x가 들어있으면 1, 없으면 0을 집어 넣으면 2진수가 된다.

사실 당연한게, 10(2)이 되려면 0부터 시작해서 1을 두번 더해야하고, 100(2)이 되려면 앞서 두번더한 행위를 (10(2)) 또 두번 해야하기 때문이다(2 x 2 = 22). 이런식으로 하다보면 위와같이 10진수를 2x와 마지막 1(20)로 표현할 수 있다.

결국 10진수를 2진수로 표현하려면, 그 숫자안에 2x가 포함 되어 있는지 아닌지를 바탕으로 1혹은 0을 왼쪽(큰쪽)에서 오른쪽(작은쪽)으로 체워나가면 된다. 그렇다면 22를 2진수로 표현하기 위해서 맨 왼쪽에 1을 넣어야 하는데, 전체 자리수는 어떻게 알 수 있을까? 해답은 2로 나눌 수 있을 때 까지 나누는것이다. 홀수가 나오면 1을 빼고 또 나눠보는것이다.

2를 계속 나눠봄으로써 22안에 2x로 표현할 수 있는 숫자중 제일 큰 24가 들어가있다는것을 알 수 있다(그래서 맨 앞에 1을 적음). 나는 2로 막 나누는데 홀수가 나올때 1을 빼는것에 대해서 처음에 조금 불편하게 느껴졌다. 하지만 단순히 22안에 가장큰 2x 를 구하는것이기 때문에 홀수일때 1을 빼는건 상관 없을것 같다. 왜냐하면 그 1을 뺀것 때문에 22안에 들어갈 2x 중 가장 큰게 24 라는것에는 영향을 끼치지 않기 때문이다. 어떤 수학 공식으로 표현할수는 없지만, 느낌상 그렇다( 2x > x 이런건가??). 33333을 2로 막 나눴을때 우수수수 떨어지는 1들을 모아도 절대 가장큰 215(32,768)를 넘을 수는 없을것이다.

이제 맨 왼쪽을 채웠으니 그 다음에 22안에 23, 22, 21, 20이 들어있는지 확인해서 들어있으면 해당 자리에 1을 넣고 없으면 0을 넣으면 된다. 방법은 심플하다(구현은 복잡..). 24는 구했으니까 22에서 24를 뺀값(=6)안에 23이 들어있는지 체크해서 들어있으면 1 없으면 0넣고 그 다음에는 (23이 안들어 있으니까 빼지 않고) 6안에 22가 들어있는지 체크해서 들어있으면 1넣고 없으면 0을 넣으면 된다. 이런식으로 계속 해주면 된다.

다 채우고 난 후의 모습

조금 더 스마트하게 변환하기

22안에 들어있는 2x를 찾아가는 컨셉은 그대로이나, 순서는 반대로 하면서 더 편하게 할 수 있다. 왼쪽부터 넣을때는 가장 큰걸 먼저 찾고 막 빼면서 남은값에 2x가 들어있는지를 판별했는데, 오른쪽부터 넣을때는 제일 작은 20을 넣어도 되는지 알아보고 넣고, 그 다음에 21을 넣어도 되는지 알아보고 넣고 … 22를 넘기 전까지 계속 이런식으로 검사해서 넣으면 된다.

12x을 넣어도 되는지 안되는지는 2로 (x+1)번 나눴을때 딱 나누어 떨어지는가를 판단해서 알 수 있다. 예를들어, 22같은 경우, 처음에 2로 한번 나눴을때 딱 떨어 지니까 20은 넣지 않는다. 그리고 남은 22(22 – 0)를 두번 나눴을때( 22 -> 11 -> 5.5 ) 딱 떨어지지 않으니까 21는 집어 넣는다. 남은 20(22 – 21)을 세번 나눴을때 (20 -> 10 -> 5 -> 2.5) 딱 나눠 떨어지지 않기 때문에 22를 넣는다. 16(20 – 22)을 네번 나눴을때 (16 -> 8 -> 4 -> 2 -> 1) 딱 나눠 떨어지기 때문에 23을 넣지 않는다. 16을 다섯번 나눴을때 (16 -> 8 -> 4 -> 2 -> 1 -> 0.5) 로 딱 나눠떨어지지 않기 때문에 넣는다 !. 다만 나눈 결과값이 1보다 작으면 마지막이라는 의미이기 때문에 거기서 멈춘다, 보기쉽게 표로 정리하면 아래와 같다.

2x변화과정(x + 1번 나눔)나눠떨어지는가?
(0 = yes, 1 = no)
2022 -> 110
2122 -> 11 -> 5.51
2220 -> 10 -> 5 -> 2.51
2316 -> 8 -> 4 -> 2 -> 10
2416 -> 8 -> 4 -> 2 -> 1 -> 0.51
결과적으로 이렇게 채워진다

그런데 이렇게 해도 되는 이유가 뭘까 ?

위에서 2x를 찾아가는 룰을 설명 했는데, 저게 제대로 작동하는 이유는 다음과 같다.

  1. 모든 10진수는 2진수로 표현 가능하다. 즉 2x겹치지 않게 전부 구성할 수 있다. 231124도, 99999도 2x의 구성요소로 표현할 수 있다.(신기하다..)

2. x+1번을 나눴을때 딱 떨어지는 경우에는 2x 가 없이도 2x+1 로 채울 수 있기 때문에 2x를 넣지 않는다. 예를들어, 위의 테이블의 23은 어찌저찌해서 얻은 16을 2로 4번 나눴을때 딱 떨어져서 넣지 않았는데, 이는 최소 24를 포함하고 있다는 의미이기 때문에 23은 넣지 않아도 된다. 오히려 넣으면 더 큰숫자(24 혹은 그 이상)가 못들어가기 때문에 22를 2x로 꽉꽉 채울 수 없게된다.

3. x+1번을 나눴을때 딱 떨어지지 않는 경우에는 2x 가 마지막이거나 2x가 없으면 다음 2x+1로 채워도 빈틈이 생겨버린다. 그래서 꼭 2x를 넣어줘야한다.

4. 이전의 값들을 계속 빼주는 이유는 10진수를 2진수로 남은부분을 채워야 하기 때문이다.

사실 1번 전제가 제일 중요하다. 22라는 박스를 왼쪽부터 2x로 작은순서대로 채울 수 있다는것을 전제로 해야 2번 3번이 말이 된다. 다만, 왜 빈틈이 생길수 밖에 없는지는 사실 잘 모르겠다. 그냥 그럴것 같고, 실제로 그렇다. (장황하게 설명했지만 빈약한 논리…)

더 심플하게

사실 위와 같이 하는것은 맨 처음에 가장 큰 2x를 구하는 과정과 똑같다.

저 1들이 바로 2로 x+1번 나눴을때 딱 나누어 떨어지지 않았다는 표시이고, 0은 딱 나누어 떨어졌다는 표시이다. 그러므로 물음표 박스에 그냥 나머지값들을 넣어주면 된다.

결국 22를 2로 계속 나누고 나머지 값들만 구하면 끝이다!

너무 심플하고 속도도 빠르다 !

마무리

인터넷에 쳐보면 10진수를 2진수로 바꾸는 방법이 나와있다. 다만, 왜 그렇게 되는지에 대한 과정이 생략된게 많은것 같아서 내가 직접 길~게 알아보았다. 쉬워보였지만 나에게는 상당히 골치아픈 문제였다. 다행이 잘 풀어낸것 같아서 뿌듯하다.

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다

Up Next:

Unbuntu + Node.js + MySQL

Unbuntu + Node.js + MySQL