[만화가 있는 C] 3. 이진수

3. 이진수binary number.

  이 장의 앞 부분은 아래의 책에서 인용한 것입니다.

김용운, 김용국, “재미있는 수학 여행:①수의 세계”, 김영사, 1990, p.59.

  옛날 중국과 우리 나라에서는 모든 것을 음양으로 나누어서 따지는 경향이 강했으며, 지금도 그 전통이 뿌리 깊게 살아 있습니다. 우리 나라의 태극기가 이것을 잘 상징하고 있습니다.

팔괘(八卦)

  옛날에는 두 가지 막대를 써서 앞으로 일어날 좋고 나쁜 일을 점쳤는데, 이것을 역(易)이라고 부릅니다. 우리 나라 태극기의 네 구석에 있는 것은, 이 역의 원리의 일부입니다. 팔괘라고 부르는 이 원리는 위의 8가지인데, 지금 “-”(양)을 1, “–”(음)을 0으로 생각하고 고쳐 쓰면,

111, 011, 101, 001, 110, 010, 100, 000

과 같이 되어, 2진법의 0부터 7까지의 수와 꼭 들어맞습니다. 이 사실을 처음으로 지적한 사람은 독일의 철학자 라이프니쯔(Leibniz, 1646-1716)였습니다.

  음양 사상이란 태양과 달, 남자와 여자, 홀수와 짝수 등과 같이 세상의 모든 것을 음과 양으로 분류해서 생각하는 태도입니다.

  이 음양 사상이 유럽으로 전해졌으며, 위대한 철학자와 과학자 중에는 그 영향을 받은 사람이 적지 않았습니다. 그 대표적인 예가 라이프니쯔에 의해 발명된 2진법입니다. 지금의 컴퓨터의 논리적 구조는 2진법인데, 이 2진법이 수학이 사실은 동양의 음양 사상의 영향을 받아 태어났다는 사실은 아주 흥미를 끕니다.

  지금 이 생각을 정수에 국한시켜 생각하면 모든 정수는 짝수와 홀수로 나누어 생각할 수 있습니다. 짝수의 대표로 0, 홀수의 대표로 1을 뽑아 봅니다. 이 두 수 사이의 덧셈과 곱셈을 생각하면 다음 표와 같이 나타납니다.

+

0

1

×

0

1

0

0

1

0

0

0

1

1

2

1

0

1

  위의 표를 보면 1+1=2인 경우만을 제외하고 계산 결과는 모두 0 아니면 1입니다.

  2는 짝수이기 때문에 이것을 짝수의 대표 0으로 바꾸어 놓아 봅시다. 즉,

1+1=0

이라고 해 봅시다. 그러면 이 덧셈표는 아래 표와 같이 됩니다.


+

0

1

0

0

1

1

1

0

  이것은 아래의 표에서 짝수, 홀수를 0, 1로 바꾸어 놓은 것입니다.

+

짝수

홀수

×

짝수

홀수

짝수

짝수

홀수

짝수

짝수

짝수

홀수

홀수

짝수

홀수

짝수

홀수

  이렇게 함으로써 두 원소 0과 1로 된 집합

{0, 1}

에서 덧셈과 곱셈이 정해지고 계산의 결과도 이 집합의 테두리 안에서 얻어지게 됩니다.

  정수 전체로 된 집합을 Z로 나타내 봅시다. 즉,

Z={…, -4, -3, -2, -1, 0, 1, …}

이에 대해서 위의 두 원소로 된 집합을 Z2로 나타내 봅시다. 즉,

Z2={0, 1}

  Z2라는 집합은 Z의 원소를 짝수, 홀수라는 성질에 의하여 두 종류로 나누어 이 종류에 대해서만 생각하여 얻은 작은 집합입니다.

  이 세상 모든 것에 수를 대응시키고 이것을 짝수, 홀수로 분류하여 0과 1만으로 대표시킨 생각은 이 세상 모든 것을 음과 양으로 분류시킨 것과 근본적으로 같은 생각입니다.


보충해 주는 수: 보수(complement of a number)

  r진수 m자리수 n의 보수는 아래와 같습니다.

rm-n

  10진수에 대해서 생각해 보면, 7의 보수는 101-7=3입니다. 77의 보수는 102-77=33입니다. 10이나 100을 만들기 위해 보충해야 하는 수가 각각 3과 33이라는 의미입니다.

  보수는 뺄셈을 위해 사용할 수 있습니다. 예를 들어 10진수 8-3을 계산한다고 하면, 8+(3의 보수)=8+7=15 인데 1자리의 뺄셈이므로 십의 자리 1을 버리면,

 올림수(Carry)를 무시한다고 합니다. 2진수 2의 보수 뺄셈에서 올림수는 무시합니다.

8+7=5가 되어 원하는 결과를 얻습니다. 보수의 이러한 성질 때문에 컴퓨터는 음의 정수(Integer)를 나타내기 위해 보수를 사용합니다.

  2진수 표현에서 1의 보수(1’s Complement)와 2의 보수(2’s Complement)를 구하는 것은 쉽습니다. 1의 보수는 단순히 1과 0을 토글(Toggle)시킴으로 구할 수 있고, 2의 보수는 1의 보수를 구한 다음, 결과에 1을 더하면 구할 수 있습니다. 예를 들어, 1001011100의 1의 보수는 0110100011이며, 2의 보수는 0110100011 + 1 = 0110100100입니다.

  2의 보수는 더 간단하게 구하는 방법이 있는데, 오른쪽에서 왼쪽으로 처음으로 1을 만날 때까지 스캔(Scan)하며 만난 숫자를 적다가, 처음 1 이후의 모든 비트를 토글(toggle)하면 됩니다.


 2의 보수를 구하는 법

  컴퓨터가 정수를 나타내는 방식은 일반적인 2진수 체계를 따르지만, 음수를 나타내기 위해서 2의 보수를 사용합니다. 2진수 n비트로 나타낼 수 있는 수의 범위는 다음과 같습니다.

0~2n-1

 2개에서 n개를 뽑아내는 중복 순열의 수이므로 2󰍎n=2n입니다. 숫자는 0부터 시작하므로 최고 큰 수는 1을 빼주어야 합니다.

  그러므로 unsigned char형은 0~28-1, 즉 0~255를 나타낼 수 있고, unsigned short int형은 2바이트이므로, 0~216-1, 즉 0~65535를 나타낼 수 있습니다. 음수인 경우는 어떻게 할까요? 음수인 경우는 가장 중요한 비트(Most Significant Bit: MSB)를 부호 비트(Sign Bit)로 사용하여, MSB가 1인 경우는 이 수의 2의 보수를 취한 값을 음수로 취합니다. 즉 부호는 음수로 결정된 상태에서 이 수의 2의 보수를 구하여 값을 취하므로, MSB자체도 값의 결정에 사용될 수 있습니다. 부호 있는 3비트로 1의 보수와 2의 보수로 각각의 정수를 표현해 보면 아래 표와 같습니다.


1의 보수

정수값

2의 보수

정수값

000

001

010

011

100

101

110

111

+0

+1

+2

+3

-3

-2

-1

-0

000

001

010

011

100

101

110

111

+0

+1

+2

+3

-4

-3

-2

-1

 1의 보수와 2의 보수의 부호 있는 정수값

  예를 들어, 101의 경우 1의 보수에 대해서,

MSB가 1이므로 음수

101의 1의 보수는 010=2

이므로 -2가 됩니다. 하지만 2의 보수에 대해서는,

MSB가 1이므로 음수

101의 2의 보수는 011=3

이므로 -3이 됩니다. 디지털 컴퓨터가 2의 보수를 이용하여 정수를 표현하는 이유는 올림수를 무시해도 되는 이점 때문입니다. 예를 들어 3-2를 하는 경우 1의 보수인 경우,

011+101=1000

밑줄 친 것처럼 올림수가 발생한 경우 이를 다시 더해야 합니다. 그러므로,

000+1=001

이 되어 원하는 결과 1을 얻을 수 있습니다. 하지만 2의 보수인 경우는 단순히 올림수를 무시하면 되므로 +연산을 적게 사용하므로 효율적입니다.

 2의 보수에서 올림수의 무시

  2의 보수로 수를 표현했을 때, n비트의 부호있는 정수의 범위는 다음과 같습니다.

-2n-1~2n-1-1

  그러므로, signed short int인 경우 -32768(-215) ~ 32767(215-1) 범위의 수를 표현할 수 있습니다. 그렇다면, 아래 프로그램의 결과는 얼마가 인쇄될까요?


 

#include <stdio.h>

void main() {
    char c=129;
    printf("%d\n", c);
}

 

  129는 2의 보수로 0000 0000 1000 0001 입니다.

 일반적인 십진수는 컴파일러가 4바이트 정수형으로 간주합니다. 8바이트 정수를 만들려면 숫자의 끝에 UL을 붙여야 합니다. 예를 들어 3은 4바이트로 간주하지만, 3UL은 8바이트로 간주합니다.

이 숫자를 8비트 char변수 c에 대입하는 과정에서 상위 8비트는 잘려집니다.

 자동으로 형 변환이 된다고 하여 자동 형 변환(automatic type casting)이라고 합니다.

그러므로 c는 1000 0001입니다. 이것을 printf가 출력하는데 부호 있는 정수형이므로 2의 보수 체계를 따라 다음과 같이 계산합니다.

        MSB가 1이므로 음수

        1000 0001의 2의 보수는 0111 1111=127

그러므로 -127이 출력되는 것입니다.


 진보된 주제: 비트 플래그(bit flag), 비트 마스크(bit mask)

  아래에 설명하는 내용들은 아직 우리가 이해할 수 없는 내용이므로, 일단은 건너뛰었다가, 10장의 ‘제어구조’까지 본 후에 다시 살펴보기 바랍니다.

  위에서 설명한 2진수의 개념이 프로그램에 어떻게 이용되는 것일까요? 2진수는 프로그래밍에서 많이 이용됩니다. 그리고 디버깅debugging을 위해서 메모리를 덤프dump한다든지 했을 때 우리가 보는 데이터들은 2진수와 대응되는 16진수입니다. 그러므로 2진수와 친숙해 지는 것은 중요합니다.

  아래의 프로그램은 구구단을 출력하는 프로그램인데 구구단을 출력하다가 사용자가 임의의 키를 누르면 종료하도록 만들려고 합니다. 아래에 설명 부분을 보지 말고 직접 고쳐보기 바랍니다.


#include <stdio.h>
#include <conio.h>

void main() {
    int i=1,j;
    //clrscr();
    while (i<100) {
        ++i;
        j=1;
        while (j<100) {
            printf("%5d*%5d=%8d",i,j,i*j);
            ++j;
        }//while
    }//while
}

 

  두 번째 while문을 탈출하도록 논리를 구성해야 하는데, 단순하게 두 번째 while문안에서 break를 사용하는 것은 문제를 해결하지 못합니다.

if (kbhit()) break;

break는 자기를 둘러싼 가장 가까운 반복 구조의 블록을 탈출하기 때문입니다. 즉 위와 같이 사용한 break는 두 번째 while문을 탈출하기만 할 뿐입니다.

 반복 구조는 for, while, do…while이 있습니다. break는 이들 문장을 탈출하며, switch에 쓰인 break는 특성이 다릅니다.

그러므로 두 번째 while문에서 어떤 사건이 발생했다는 것을 기억시키기 위해서 특정한 변수를 사용해야 합니다. 변수가 이러한 목적으로 사용되었을 때 깃발(Flag) 변수라고 합니다. 플래그flag를 사용한 소스를 아래에 리스트 하였습니다.

 특정한 사건이 발생했음을 깃발로 알린다는 뜻에서 유래하였습니다.


#include <stdio.h>
#include <conio.h>

void main() {
    int i=1,j;
    int flag=0;//사건을 기록하기 위해서 사용합니다.
    //clrscr();
    while (i<100) {
        ++i;
        j=1;
        while (j<100) {
            printf("%5d*%5d=%8d",i,j,i*j);
            ++j;
            if (kbhit()) {
                flag=1;
                break;
            }//if
        }//while
        if (flag==1) break;//사건이 일어난 경우 while을 탈출한다
    }//while
}

 

  어떤 정수형 변수의 이진 비트열의 각각의 비트들이 이러한 깃발 변수로 사용되었을 때를 비트 플래그bit flag라고 합니다.

  예를 들어 정수형 변수 short는 16비트이므로 16가지의 on/off 상태를 기록할 수 있습니다. 만약 상태의 개수가 4가지라면, 상태를 나타내는데 2비트가 필요하므로 하나의 short정수를 8가지의 깃발 변수로 사용할 수 있습니다.

  예를 들어 컴퓨터 바둑 프로그램을 구현할 때 판(Board)의 각각의 위치에 대해, 아래의 정보를 유지한다고 합시다.

  (1) 판의 현재 상태: 2비트(비었음, 검은돌, 흰돌, 가장자리)

  (2) 이웃한 검은색 돌의 수: 2비트(Neumann이웃이므로 최대 4까지 가능)

  (3) 이웃한 흰색 돌의 수: 2비트

  (4) 덩어리 번호: 8비트

  (5) 마킹을 위한 임시 비트: 2비트

  그러면 우리는 정수형 배열 board[19+2][19+2]을 선언해서 각각의 판 위치에 대해 아래 그림처럼 정보를 유지할 수 있습니다.

 가장자리를 고려해야 하므로 줄과 열에 대해, 19+2가 필요합니다. 실제로는 눈목자(目)등의 변위도 고려해야 하므로 19+6등으로 구현합니다.

 컴퓨터 바둑에서 판이 유지하는 정보

  얼마만큼의 공간이 효율적인가요? 위처럼 사용하면 board가 차지하는 메모리는 21×21=441 바이트입니다. 만약 우리가 비트 플래그를 몰라서 구조체 배열을 사용한다면, 아래와 같이 구조체structure를 작성할 수 있습니다.



    struct BOARD {
        char nState, nBlack, nWhite;
        unsigned char nGroup;
        char nMarking;
    } board[21][21];

 

각각의 자리마다, 5바이트를 사용하므로, 21×21×5=2205 바이트를 사용해야 합니다. 또한 공간만이 문제가 아니라 함수의 파라미터 수 등이 문제가 될 수 있습니다.

  다음으로 우리가 고려해야 할 문제는 ‘어떻게 각각의 비트 플래그를 갱신하는가?’입니다.

 board[y][x]의 상태

  예를 들어 위 그림과 같은 상태의 board[y][x]의 값은, 다음과 같습니다.


 배열의 첫 번째 인덱스가 행을 나타내므로, y좌표가 되어야 합니다.

00 00000100 10 01 01

이것은 (x,y)에 검은 돌이 있으며, 4-연결 이웃에 각각 검은돌, 흰돌이 1개, 2개 있음을 나타내며, 덩어리 번호는 4임을 나타낸니다. 이 상황에서 4의 마지막 남은 이웃 자리에 검은 돌을 놓았다고 합시다. 그러면, 다음과 같이 갱신해야 합니다.

00 00000100 10 10 01

어떻게 밑줄 친 비트의 일부만을 갱신할 수 있을까요? 절차는 다음과 같습니다.

  (1) 갱신하고자 하는 비트열만을 일반 정수 형태로 변환합니다.

  (2) 변환된 정수를 갱신합니다.

  (3) 갱신된 정수 비트열을 원래 자리에 다시 가져다 놓습니다.

이를 갱신하는 루틴은 아래와 같이 쓸 수 있습니다.


  unsigned int i=board[y][x];//i= 00 00000100 10 10 01
  unsigned int t;
  t=(i & 0x000c)>>2;//0x000c는 이진수로 0000 0000 0000 1100입니다.
  ++t;//t가 1에서 2가 됩니다.
  i=(i & 0xfff3) | (t<<2);//0xfff3은 이진수로 1111 1111 1111 0011입니다.
  board[y][x]=i;

 

  비트 연산자에 대해서 알고 있다고 하더라도, 위의 코드를 처음 보면 이해하기 힘들 수도 있습니다. 하지만 위의 코드는 비트 마스크bit mask의 조합에 불과합니다. 비트 마스크는 비트 연산자 &, | 를 사용하여 특정한 비트를 1로 혹은 0으로 만드는 것을 말합니다. & 와 | 연산은 아래와 같은 특징을 가집니다.

 비트 마스크의 원리

  즉, 1과 & 하면 원래의 비트가 유지되며, 0과 & 하면 모두가 지워집니다. 또한 1과 | 하면 모두가 1이 되며, 0과 | 하면 원래의 비트가 유지됩니다. 이러한 원리를 이해하면 위의 소스 코드를 이해할 수 있습니다.


 실습문제


1. 아래의 출력 결과는 얼마인가요?


    #include <stdio.h>

    void main() {
        int i=7;
        printf("%d\n",~i+1);
    }

 

2. 아래의 출력 결과는 얼마인가요?

 eXclusive Or 연산의 특징을 잘 파악해 두기 바랍니다. XOR 연산을 두 번 연속해서 적용하면 원래의 비트를 유지할 수 있습니다.


    #include <stdio.h>

    void main() {
        int i=0x5555, j=0x1234, k;
        k=i^j;
        printf("%x\n",k);
        printf("%x\n",k^j);
    }

 

3. 아래의 프로그램에서 Product(a,b) 함수는 a*b를 쉬프트(shift) 연산과 모듈로(modulo) 연산만을 사용하여 계산합니다. Product() 함수를 자세히 설명하세요(힌트: Booth 알고리즘).


#include <stdio.h>

long Product(long a,long b) {
    long p=0;
    while (a>0) {
        if (a%2==1) p+=b;
        a>>=1;
        b<<=1;
    }//while
    return p;
}//Product()

void main() {
    printf("%ld\n",Product(3,7));//결과는 3*7=21입니다.
}

 

@

만화가 있는 C

Leave a Reply