C 프로그래머가 알아야 할 것들 - Chapter 2 비트의 법칙

C 프로그래머가 알아야 할 것들 - Chapter 2 비트의 법칙

김성훈 (sunghun84@nate.com) 

(1) 비트가 뭐지?
비트란 이진수(Binary Digit )의 약자로써 컴퓨터에서 제어 가능한 데이터의 최소단위입니다.
하지만, 컴퓨터에서 입 출력할 때 사용하는 최소 단위는 바이트죠. 둘 다 최소단위라는 건 알겠는데 정확한 차이가 뭐냐고요?

비트란 저번 강좌에서 배웠던 2진수 10 (10진수 2)을 2비트(2진수 2자리 수이기에)로 표현 가능하고 제어 가능하단 의미고, 바이트는 비트 8개가 모여서 구성된 것이 1바이트로, 파일이나 데이터 형의 최소단위로 쓰입니다.

(2) 프로그래밍과 비트는 무슨 상관일까?
비트가 2진수를 의미한다는 건 알겠는데 도대체 프로그래밍에서 비트가 무슨 의미가 있는 것인지 궁금해하실 분들이 계실 거라고 생각합니다.

하드웨어의 발전에 따라 조금 더 빠른 프로그램 보다는 쉬운 사용법과, 코드 재사용 또는 유지 보수가 쉬운 프로그램을 만드는 것이 더 중요해졌고, 그로 인해 C++을 대신할 차세대 언어라 불리는 자바, C#이 등장했습니다. 하드웨어가 발전함에 따라 그 하드웨어의 기능을 활용하기 위한 기술이 적용 되다 보니 여전히 빠른 프로그램을 작성할 필요성은 존재합니다.

속도 면에서 타의 추종을 불허한다는 C/C++에서도, 속도 최적화에 크게 민감하지 않은 자바에서도, 코드 수행의 근본적인 속도 문제는 벗어 날 수 없습니다.

어떤 언어를 사용하건 간에, 결국엔 기계어로 번역되어 수행되기 때문에 가능하다면 빠르고 효율적인 프로그램을 작성하도록 하는 것이 좋습니다.

대부분의 알고리즘은 N (임의의 수)에 비례해서 수행속도가 증가하는데, N이 증가할 때마다 제곱으로 수행 시간이 증가해 100년 이상 걸려야만 수행이 완료되는 경우도 있기에 여전히 프로그램의 수행 시간은 중요합니다.

최적화 된 프로그램이란 메모리와 속도 모두 만족시키는 프로그램을 말하는데, 그것을 만족하기 위해선 비트 단위 연산 또는 처리가 필요 할 때가 많기 때문에, 비트 연산에 대해서도 알아 두는 것이 좋다고 볼 수 있는 것이죠.

(3) 데이터 형
C언어에서는 다양한 데이터 형을 제공합니다.
여기서는 주로 사용되는 몇 개의 데이터 형만 가지고, 비트와 관련해 알아보도록 하죠.

문자 형으로 알려진 char (캐릭터 형)는 1바이트로 이루어져있습니다.
1바이트=8비트이므로, 0000 0000 이렇게 8자리 2진수만큼 사용할 수 있는데, 2의 7승은 256 (첫 자리가 2의 0승이므로, 8비트의 경우 2의 7승만큼 사용 가능합니다) 이므로, 부호가 없는 경우는 0~255, 부호가 있는 경우는 -128~127까지 사용 가능하게 되는 겁니다. 부호가 있는 경우는 최상위 비트를 부호 비트로 사용하게 되므로 사용 가능한 수의 범위가 반으로 줄 게 됩니다.

2바이트 데이터 형인 short int 도, 2의 15승인 65536만큼의 수를 사용할 수 있는데, 부호 없는 경우 0~65535, 부호가 있는 경우 -32768~32767까지의 수를 사용할 수 있습니다.

데이터 형	크기(바이트)	부호	표현 범위
int	4	있음	-2147483648~2147483647
short int	2	있음	-32768~32767
long int	4	있음	-2147483648~2147483647
unsigned int	4	없음	0~4294967295
unsigned short int	2	없음	0~65535
signed char	1	있음	-128~127
unsigned char	1	없음	0~255

위 표에서 알 수 있는 것은, C언어 계열에서는 별도 표기를 하지 않는 이상 signed(부호 있는)로 인식한다는 점 입니다.

실수 형은 단순히 2진수로 데이터를 담고 있지 않습니다.
다음과 같은 형식으로 실수를 표현하고 있습니다.

부호

지수부

가수부

부호는 말 그대로 +- 부호를 의미하고, 가수부는 값을 의미합니다. 지수부는 10의 거듭승을 의미합니다.

좀 더 정확히 말하자면, 지수부는 그 자체가 지수부의 값이 아니라 이 수치에서 bias 값을 빼 주어야 그 값이 나옵니다. 일반적으로 float에서 bias의 값은 127 입니다. 가수부는 가장 좌측의 값이 2⁰를, 그 다음이 2^-1, 그 다음은 2^-2… 입니다.

부호를 s, 지수부를 e, bias를 b, 가수부를 m 이라고 한다면 그 값은

(-1)^s * 1.m * 2^{e - b}
로 표현하면 됩니다.

6 을 부동 소수점 실수로 표현해봅시다.

6 = 1.5 * 2^2 = 0100 0000 1100 0000 = 40 C0

부동 소수점 실수를 우리가 일반적으로 사용하는 인텔 프로세서에서 float형으로 표현할 경우, 순서가 조금 다릅니다.

6.0f = 0000 0000 0000 0000 1100 0000 0100 0000 = 00 00 C0 40

이를 리틀 엔디안 표기법이라고 하구요, 이는 6번째 주제로 다루고 있으니 거기서 더 자세히 얘기해보도록 하고 넘어가죠.

 

데이터형	크기(바이트)	표현 범위
float	4	3.4*10-38~3.4*1038
double	8	1.7*10-308~1.7*10308
long double	10~16	1.2*10-4932~3.4*104932

실수 형의 경우 값의 표현 범위가 넓은 대신 정밀도가 떨어지고 오차가 존재합니다. 그렇지만 고정 소수점 소수에 비해 표현 범위가 넓은 것이 장점이 되어 현재 사용되고 있습니다. 어떤가요? 도움이 조금 되시나요?
 
이렇듯 컴퓨터에서 사용되는 데이터들은 모두 비트 기반으로 이루어져 있습니다.

(4) 바이트로 구성된 파일
비트 8개가 모여서 만든 바이트가 모여서 만들어진 것이 파일입니다.
우리가 흔히 사용하는 이미지 파일들도 알고 보면 색상 정보를 담고 있는 바이트의 집합입니다. 여기서 조금 부연 설명을 하자면, BMP(비트맵)파일의 경우는 헤더나 컬러 테이블 정보도 담고 있긴 하지만, 일반적으로는 RGB색상 값만 가지고 있다고 보시면 됩니다. RGB 색상 값은 Red 1바이트, Green 1바이트, Blue 1바이트씩 저장됩니다.

색상 값을 가지고 있다가 프로그램에서 BMP파일을 읽어 들였을 때, 색상 정보를 읽어서 RGB색상 값을 조합 한 후 점을 찍어서 (BitBlt함수로도 찍을 수 있는데 라고 생각 하실 분도 있으시겠지만, BitBlt함수도 결국 내부적으론 점을 찍어서 표현해줍니다) 그 색상을 모니터에 표현하도록 명령을 내려주기 때문에, 우리 눈에는 컬러 이미지를 볼 수 있는 겁니다.

저장되어 있는 RGB색상 값을 아무런 압축도 하지 않고 모두 가지고 있는 경우가 위에서 설명한 BMP파일 포맷이고, JPG의 경우는 고도의 압축 기법(압축률도 지정 가능 합니다)을 통해서 용량을 줄였지만 결과적으로는 색상 값을 가지고 있다 신장(압축해제)후 화면에 뿌려주는 원리는 비슷합니다.

벡터 그래픽 파일의 경우에는 점, 선, 곡선 등의 정보를 저장하고 있는 포맷이지요. 그래서 화면에 축소나 확대에서도 같은 이미지를 볼 수 있는 것 이지요.

동영상 파일도 많은 양의 그림 정보를 담고 있다가, 1초에 몇 번 이상(1초에 몇 번 화면이 갱신되는지를 프레임이라고 하는데, 초당 24내지 30프레임은 되어야 깜빡임이 사람 눈에 보이지 않는다고 합니다. 일반적으로 모니터의 경우는 60번 이상 갱신되고 있죠)갱신되는지에 따라 그것을 재생시켜줍니다.

음악파일도 마찬가지로, 소리 정보를 디지털 값(수치 값)으로 가지고 있다가, 그 정보를 재생시간에 맞춰 재생하는 방식을 취하고 있죠.

Star Craft의 Replay 파일의 경우에도 비슷하게 첫 위치 값을 저장한 후에 거기서 변화한 값과 내린 명령,시간 값들을 저장했다가, Replay 메뉴에서 재생 시 그 정보를 바탕으로 게임을 재생시키는 방식을 취합니다. 그래서 Replay파일의 용량이 그다지 크지 않은 것입니다.

게임 세이브 파일의 경우에도, 그 캐릭터의 레벨, 무기 일람, 체력, 공격력, 방어력 등의 Parameter와, 그 캐릭터의 현재 위치, 플레이 시간 등의 정보를 저장하고 있습니다. 물론 Edit가 힘들 게 하기 위해 단순한 파일 구조(순차적)으로 구성하지 않는 경우가 대부분이긴 하지만요.

핵심은 모든 데이터는 바이트 단위로 저장된다는 것. 그 바이트를 구성하고 있는 것은 비트라는 것입니다.

(5) 비트 연산자
자 비트에 대해 배웠으니 비트 연산을 한번 해봐야겠죠?
기본적으로 C언어에서의 대입은, 데이터 형 단위로 제어가 되죠. 하지만, 비트 연산이란, 비트 단위로 데이터를 제어하는 것을 말합니다.

비트연산에 사용되는 비트연산자란 논리 곱 (&) , 논리 합 (|), 논리 부정 (~), 베타적 논리합(^)이 있습니다. 부울 대수를 배우셨던 분들은 익숙하실 겁니다.

논리곱(AND : &) 둘 다 1일 때만 참(TRUE)이 됩니다.

입력 값 1	입력 값 2	결과
0	0	0
0	1	0
1	0	0
1	1	1

논리합(OR : |) 둘 중에 하나라도 1이면 참(TRUE)이 됩니다.

입력 값 1	입력 값 2	결과
0	0	0
0	1	1
1	0	1
1	1	1

베타적 논리합 (XOR : ^) 두수의 값이 달라야만 참(TRUE)이 됩니다.

입력 값 1	입력 값 2	결과
0	0	0
0	1	1
1	0	1
1	1	0

논리 부정 (NOT : ~) 0은 1로, 1은 0으로 만들어줍니다.

입력 값	결과 값
1	0
0	1

비트의 위치를 이동 시키는 시프트 연산자 (SHIFT) 라는 것도 있습니다.

좌측 시프트 연산자 (<<)는 비트를 왼쪽으로 옮겨주고, 빈자리엔 0을 넣어줍니다.

0011 0010 << 2

0011 0010 (10진수 50)에 <<연산자로 비트를 왼쪽으로 두 번 옮겨보겠습니다.

1100 1000

왼쪽으로 2번 이동했더니 수가 10진수 200이 되었습니다. 시프트 하기 전 값에 4배 (50 x 4 = 200)가 되었죠? 비트를 왼쪽으로 한번 옮길 때마다 수가 2배가 된다는 것을 아실 수 있을 겁니다.

우측 시프트 연산자 (>>)는 비트를 오른쪽으로 옮겨줍니다. 오른쪽 시프트의 경우는 좌측 시프트와는 다르게 항상 0 이 들어 가는 것이 아니라. (시프트 하는 데이터 타입이 무엇인가에 따라, 혹은 컴파일러에 따라 다릅니다) 일반적으로, unsinged 타입일 경우 -> 0 이 들어가고 (`논리적 시프트`), singed 타입일 경우 첫 비트가 1 이면 1을 0이면 0을 채우게 됩니다. (`산술적 시프트`)

0011 0011 >> 2

0011 0010 (10진수 50)에 >> 연산자로 비트를 오른쪽으로 두번 옮겨보겠습니다.

0000 1100

우측으로 2번 이동했더니 수가 0000 1100 (10진수 12)가 되었습니다. 4분의 1(12.5여야 하지만, 소수점 이하는 버립니다) 이 되었죠?

이렇게 됩니다.

(6) 생각보다 간단한 압축
압축방법에는 Run Length Code, Huffman Code 등 다양한 방법이 있지만, 여기선 시프트 연산자와 비트 연산자의 조합으로 간단한 압축을 구현해보겠습니다.

아까 데이터를 압축하려면 현재 데이터에서 변화한 정보를 담는 것이 좋다고 했었죠? 그 원리를 이용하는 것입니다.

주로 다른 파일보다는 이미지, 음악 파일, 동영상 파일 등에 사용되는 데이터 압축의 원리는 이 바이트를 기본으로 한 데이터들이 비트로 이루어져있다는 것이 핵심입니다.

런 렝스 코드 (Run Length Code)는 특정 값이 몇번 반복되는지를 저장하는 방식입니다.

AAAABCCDDDEEEFFFFFFF

라는 데이터가 있다면,

A4B1C2D3E3F7

로 원래 데이터와 반복 횟수를 표기하는 방법입니다.

문자열 반복이 잦다면 압축률이 높겠지만, 문자열의 반복 빈도가 낮다면 런 렝스 코드를 적용했을 때 용량이 더 커지기도 합니다.

ABCDEFG

라는 문자열이 있을 때, 이 문자열을 런 렝스 코드를 사용하면,

A1B1C1D1E1F1G1

이렇게 반복이 없을 땐 오히려 용량이 두 배가 되기 때문이죠.

허프만 코드(Huffman Code)는 자주 사용되는 문자를 짧은 코드로, 덜 사용되는 문자를 긴 코드로 변환해서 압축하는 방법의 압축 법입니다.

AAAABCCDDDEEEFFFFFFF

위 데이터가 있을 때, 원래 대로 라면 21바이트가 필요하겠죠?

허프만 코드를 이용해서 표현해보겠습니다.

AAAA B CC DDD EEE FFFFFFF

반복 횟수가 적은 순에 따라 비교해가며 값을 대입해주면, 아래와 같은 결과를 얻을 수 있습니다. (같은 값 처리나, 트리 만들어 나가는 과정은 세부 알고리즘에 따라 다릅니다. 현재는 같은 값일 경우 왼쪽에 위치한 값을 더 작다고 판정하였습니다.)

데이터	변환된 값	변환된 비트 크기	반복횟수	소요 비트
F	0	1	6	6
A	10	2	4	8
E	110	3	3	9
D	1110	4	3	12
C	11110	5	2	10
B	11111	5	1	5

위 표와 같은 결과를 얻게 됩니다. 다 더하면 6 + 8 + 9 + 12 + 10 + 5 = 50바이트. 21바이트 였던 168 비트보다 무려 118 비트나 적게 소요되었죠?

이렇듯, 컴퓨터의 모든 데이터는 비트 기반 위에 존재 하기에, 비트의 존재를 꼭 기억해두세요.