진법 변환 - 정보올림피아드 문제풀이

진법은 수를 표현하는 방법을 나타내는 것으로 일상 생활에서 일반적으로 사용하는 진법은 10진법입니다. 십진수 2345는 다음과 같이 표현 할 수 있습니다.

위의 식은 각 진법을 지수 형태로 표현한 것입니다. N진수를 10진수로 변환하는 방법은 위의 식과 같이 N진수의 각 자릿수에 해당하는 밑수 N(base)을 n제곱한 값에 각 자리의 값을 곱한 결과를 합산하는 것입니다. 모든 밑수의 의 값은 1입니다.

반대로 10진수를 N진수로 변환하는 방법은 아래의 그림과 같이 십진수를 N으로 나누면서 더이상 나누어지지 않을 때까지 나머지를 계산하고 그 결과를 배열하면 됩니다.

2진수는 맨 우측부터 3자리씩 묶으면 8진수로 4자리씩 묶으면 16진수로 손쉽게 변환 할 수 있습니다. 이런 특성 때문에 컴퓨터에서 2진수, 8진수, 16진수를 많이 사용합니다. C언에서는 8진수와 16진수 표현 법을 제공하는데 8진수는 앞에 0을 붙이고 16진수는 앞에 0x를 붙이면 됩니다. 위의 예제에서 04451은 십진수 4451이 아니라 8진수 4451로 십진 값으로는 2345이고 16진수로는 0x929로 표현합니다.

* 실수(소수부) 표현

0.678을 지수 형태로 표현하면 아래와 같습니다.

2진수나 기타 진법의 경우에도 마찬가지로 음의 지수로 표현합니다.

10진 소수를 N진수로 변환할 때는 정수부의 경우에는 N으로 나눈 나머지를 구했으나 소수부는 N을 곱한 몫을 취하는 방식입니다.

위의 그림을 보면 십진 소수 0.678을 2진수와 16진수로 변환하는 과정을 볼 수 있는데 N진수의 N을 곱하여 정수부를 취하고 다시 소수부에 N을 곱하기를 반복하는 것입니다. 0.678을 2진수로 표현하면 0.1010110110010001....으로 나오고 16진수로 표현하면 0.ad916872.... 그런데, 그림에서 확인할 수 있듯이 거의 무한대로 소수부 표현이 길어지는 것을 확인할 수 있습니다. 이런 배경 때문에 컴퓨터에서는 실수를 부동 소수점의(Floating point) 형태로 표현하고 이 과정에서 값의 오차나 손실이 있을 수 있습니다.

* 음수 표현

처음에 설명한 정수 표현은 양의 정수 즉 부호를 감안하지 않은 값의 진법 변환을 이야기 했다면 바로 위에서 컴퓨터에서의 실수 표현을 어떻게 하는지 그 개념적인 설명의 일부를 다루었습니다. 컴퓨터에서 음수 표현은 간단히 말하면 2의 보수로 표현합니다. 컴퓨터에서는 결국 내부적으로 2진수로 저장되므로 음수 표현 또한 2진수와 연관하여 이해할 수 밖에 없습니다. 특정 메모리에 저장한 데이터를 부호를 감안할 것인지, 부호를 감안하지 않을 것인지는 이미 프로그램을 작성하는 시점에 결정됩니다. 예를 들어 C언어 에서 "int a;" 라고 선언하면 기본적으로 부호 정보를 감안하겠다는 의미이고 "unsigned int a;"라고 선언하면 해당 저장 공간의 데이터를 부호를 감안하지 않고 처리하겠다는 의미로 음수를 표현할 수는 없지만 절대값으로 표현 영역은 넓어집니다.

특정 공간의 자료를 부호를 감안해서 처리하는 경우 음수 여부는 맨 꼭대기 비트(MSB, Most significant bit)의 상태로 구분하여 1이면 음수 0이면 양수로 취급합니다. 예를 들어 8비트 정수 표현으로 10010001은 MSB가 1로 음수임을 나태내며 십진수 값은  2의 보수를 취하면 됩니다. 2의 보수를 구하는 방법은 각 비트 값을 1은 0으로 0은 1로 바꾸고(1의 보수) 1을 더하면 됩니다. 예제의 1의 보수는 01101110이고 1을 더해서 2의 보수를 취하면 01101111로 십진수 111이므로 10010001를 부호 있는 정수값으로 취급하면 -111입니다. 모든 비트가 1이면 -1을 의미합니다.

* 정보 올림피아드 연관 문제 풀이

1. 2진법으로 표시된 정수 111111을 제곱한 수를 2진법으로 나타낸 수는 무엇인가?

① 111111111111 ② 111111100001 ③ 111111000001④ 111110000001 ⑤ 111100000001

단순한 방법으로 접근하면 2진수 111111를 16진수를 통해 빨리 10진수로 변환하면 3*16 + 15 = 63입니다. 63 * 63 = 3969를 계산해서 다시 2진수로 변환 할수 있습니다. 그러나, 위의 문제는 2진수끼리의 곱셈을 적용하면 더욱 빠르게 계산할 수 있습니다. 1*0=0, 0*0=0, 1*1=1인 원리를 적용하고 초등학교때 여러자리 수의 곱셈하던 방식을 적용합니다. 111111 * 111111이므로 아래와 같이 곱셈을 덧셈으로 바꿀 수 있습니다.

                    1 1 1 1 1 1

                  x 1 1 1 1 1 1

       ---------------------

                    1 1 1 1 1 1   

                  1 1 1 1 1 1 

               1 1 1 1 1 1 

             1 1 1 1 1 1

          1 1 1 1 1 1

        1 1 1 1 1 1

       ---------------------

        1 2 3 4 5 5 4 3 2 1 0(올림수)

끝 자리부터 올림수를 감안하여 더하면    111110000001로 정답은 4번입니다.

2. 다음은 문자열로 주어진 이진수를 십진수의 정수로 변환하는 프로그램이다. 예를 들어, 이진수 문자열 “101011”이 주어지면 정수 43를 반환한다. 빈 칸에 들어갈 내용으로 알맞은 것은?

int bin2Dec(char s[])

{

    int v, i;

    v = 0;

    for (i = 0 ; i < strlen(s) ; i++) _____________

    return v;

}

① v = v * 2 + (s[i] - '0');② v = v * 10 + (s[i] - '0');③ v = v * 2 + s[i];④ v = v * 10 + s[i];⑤ v = v + (s[i] - '0');

이 문제는 N진수를 10진수로 변환하는 알고리즘으로 사용하기 참 좋은 프로그램입니다. 위의 진수 변환을 보면 각 자리수 * N의 n승을 쭉 더하는 방식이었는데 문제 코드의 알고리즘은 Hornor법이라 부르는 것으로 N진수를 10진수로 바꿀때 다음과 같은 식으로 변환할 수 있습니다.

위 예제 값 101011에 대입하면 ((((1*2+0)2 + 1)2 + 0)2 + 1)2 + 1이 됩니다. 한가지 주의할 것은 입력이 문자열 이므로 문자를 숫자로 변환해 주어야 하는데 '0'문자 값에서 '0'문자 값을 빼면 숫자 0, 문자 '1'에서 문자 '0'을 빼면 숫자 1이 되는 원리를 이용하면 정답은 Hornor법 공식을 적용한 1번이 됩니다.

다음의 문제들은 연습문제로 직접 풀어보세요.

3. 다음 프로그램은 십진수 k를 삼진수 s로 바꾸어 주는 프로그램의 일부이다. 빈 칸에 알맞은 것은?

 while (k>0)

 {

   s = _________________;

   k = _________________;

 }

(1) s + (k / 3) * 10 , k % 3   (2) s + (k % 3) * 10, k / 3  (3) s * 10 + k / 3, k % 3   (4) s * 10 + k % 3, k / 3 

(5) s + k / 3, k / 3 

4. 2진수를 8진수로 바꿀 때는 이므로 2진수를 끝에서부터 세 자리씩 묶어주면 8진수로 쉽게 바꿀 수 있다. 예를 들어 2진수 10101011(2)을 8진수로 바꾸어 주면 다음과 같이 253(8)이 된다.

이와 같은 성질을 이용하여 16진수 ABC(16)을 2진수로 바꾸었을 때 1의 개수는 몇 개인가?

① 6개     ② 7개   ③ 8개  ④ 9개  ⑤ 10개

5. 다음 프로그램의 출력 결과는 무엇인가?

int n, i, b;

char str[10];

char hex[] = "0123456789ABCDEF";

n = 2014, i = 0;

for(b = 1; b <= n; b *= 16) {

  str[i++] = hex[(n / b) % 16];

}

str[i] = '\0';

printf("%s\n", str);

① 7DE  ② ED7  ③ 2014  ④ ED70  ⑤ 07DE