Chap.1 정보의 표현 - 숫자와 변수(variable)

Objectives

• 정보란?

- 언어(language): 말/문장

"한 가족이 있다. 아버지는 adam이고, 어머니는 dotty이다. 자녀의 이름은 각각 edward와 fran이다. 옆집에는 betty가 사는데 자녀는 david이다.“

- 지식(knowledge)/정보(information) - invisible

⇒ 유기체/조직체가 환경에 적응하여 살아 남아 번영하기 위한 필수조건

ex)	곤충/인간 등: 감각기관, 뇌, 유전자(DNA)

기업/국가 등: 정보수집 및 저장, 전산조직

- data/media: 인간이 ‘정보’를 표현/전달하기 위한 수단 - visible

⇒ 음성, 그림, 문자, 숫자, 영상 등

• 정보의 표현(저장): Data/Data Structure

- 정보는 사람의 뇌에 어떤 구조로 저장되는가?

We don't know yet... Why?

- 정보를 어떻게 컴퓨터에 표현할 것인가?

⇒ Digital codes

⇒ 표현의 ‘한계‘: 메모리 & 이산적(discrete)

• 정보의 처리(계산): Algorithm

- 아래의 물음에 어떻게 답할 것인가?

Q1: edward의 아버지와 어머니의 이름은?

Q2: edward 가족은 몇 명인가?

Q3: edward의 형제의 이름은?

- data structure와 algorithm은 밀접한 관련이 있다.

⇒ Algorithm의 ‘한계‘

Sample C Programs

• [부록 5] p.691 - p.696: printf()

- 특수 작업들/기호들 출력

- printf()의 형식/변환 지정자

- 정수형 출력

- 실수형 출력

- 문자형 출력

- 진법(base) 출력

• 자료형 크기: sizeof()

/* sample4.c */

#include <stdio.h>

main ( )

{  /* 자료형의 크기는 sizeof() 사용 */

printf("Type int has a size of %d bytes.\n", sizeof(int));

printf("Type char has a size of %d bytes.\n", sizeof(char));

printf("Type long has a size of %d bytes.\n", sizeof(long));

printf("Type double has a size of %d bytes.\n", sizeof(double));

}

- [C 콘서트] p.79: int의 크기는 컴퓨터/컴파일러에 따라 2 byte(16-bit computer)와 4 byte(32-bit computer)로 다를 수 있음

자료형: 수

• [부록 5] p.678 - p.681

- 정수: 음수, 0, 양수

- 실수: 유리수,

무리수- 존재하지만 표현의 '한계'가 있는 수,	e.g., ∏, √2, ℮, ∞

e.g. 초월적인 ‘존재’ - 볼 수 없는 것/들을 수 없는 것/표현할 수 없는 것

0

- 진법(base): 정수를 여러 가지 다른 표현방식으로 나타낼 수 있다.

e.g., 의미(meaning) - 여러가지 다른 언어/방법들 - arts

(684)10 = 6×102 + 8×101 + 4×100

(1101)2 = 1×23 +1×22 + 0×21 + 1×20 = (13)10

(261)8  = 2×82 + 6×81 + 1×80         = (177)10

(A3C)16 = 10×162 + 3×161 + 12×160   = (2620)10

- 10진수에서 2/8/16진수로 변환

25 = (11001)2	2 ) 25

2 ) 12   …  1

2 )  6   …  0

2 )  3   …  0

1   …  1

90 = (132)8	8 ) 90

8 ) 11   …  2

1   …  3

234 = (EA)16	16 ) 234

14  …  10

- 2진수를 8/16진수로 표현: 3개씩/4개씩

- 2진수의 연산: 덧셈

0 0 1 1 1 0 1 0

+	0 0 0 1 1 0 1 1

0 1 0 1 0 1 0 1

- 2진수의 연산: 뺄셈

⇒ 덧셈으로 변환 (1의 보수/2의 보수)

1의 보수: 0를 1로, 1을 0로 바꾼 수

2의 보수: 1의 보수에 1을 더한 수

(1 0 1 1 0 1)2 → 0 1 0 0 1 0 (1‘s complement)

0 1 0 0 1 1 (2‘s complement)

① 1의 보수 사용: 감수의 1의 보수를 더하고, 최상위 자리에서 올림수가 발생하면 결과의 최하위 자릿수에 1을 더함.

0 0 0 1 1 0 0 1	0 0 0 1 1 0 0 1

-	0 0 0 0 1 1 1 1	+	1 1 1 1 0 0 0 0

1 0 0 0 0 1 0 0 1

+	1	0 0 0 0 1 0 1 0

② 2의 보수 사용: 감수의 2의 보수를 더하고, 최상위 자리에서 올림수가 발생하면 무시함.

0 0 0 1 1 0 0 1	0 0 0 1 1 0 0 1

-	0 0 0 0 1 1 1 1	+	1 1 1 1 0 0 0 1

1 0 0 0 0 1 0 1 0

‘무시’

- 곱셈: 덧셈의 반복,

나눗셈: 뺄셈의 반복

⇒ CPU의 Adder만으로 사칙연산이 가능

• 정수

- [부록 5] p.679

- 고정 소숫점 형식 (fixed point format): 첫번째 비트는 부호, 나머지는 정수부

⇒ 소숫점은 맨 오른쪽 비트 다음 자리에 고정되어 있는 것으로 간주함.

- [C 콘서트] p.88

예) -1의 저장 방법

1 (0 0 0 0 0 0 1)2  →  1 1 1 1 1 1 1 0 (1‘s complement)

부호	1 1 1 1 1 1 1 1 (2‘s complement)

예) 뺄셈: 보수의 덧셈

① 1 - 1 = 1 + (-1)

= 0

0000 0000 0000 0001

+ 1111 1111 1111 1111

1 0000 0000 0000 0000

올림수: ‘무시’

② 32767 - 32768 = 32767 + (-32768)

= -1

0111 1111 1111 1111

+ 1000 0000 0000 0000

1111 1111 1111 1111

예) int a=1, float x=1.0;

00111111 00000000 00000000 00000000

00000000 00000000 00000000 00000001

a

x

예) 소수점 아랫수의 이진수 변환

① 소수에 2를 곱하고 결과가 1.0이면 STOP,

1.0을 넘으면 1, 넘지 않으면 0

② 1.0이 넘었으면 1을 뺌, GO TO ①

(0.15625)10=(0.00101)2	// 0.5 0.25 0.125 0.0625 0.03125

0.15625*2 = 0.3125 -- 0

0.3125*2  = 0.625  -- 0

0.625*2   = 1.25   -- 1

0.25*2    = 0.5    -- 0

0.5*2     = 1.0    -- 1	// STOP!!

• 실수: 부동(floating point) 소수점

- [C 콘서트] p.97

- [부록 5] p.680: 유효숫자, FLT_MIN, FLT_MAX, DBL_MIN, DBL_MAX

/* sample5.c */

#include <stdio.h>

#include <float.h>

int main (void)

{

float fa=0.123456789123456;	// 유효숫자 검사

double da1=0.123456789123456;	// 유효숫자 검사

double da2=1.23e+7;

printf("실수형상수: %f\n", 0.1236);

printf("실수형상수: %f\n", 3.e+3);

printf("실수형상수: %10.8lf\n", 8e-7);

// C콘서트 p.99

printf("변수: fa=%30.25f\n", fa);	// float - 7자리 유효숫자

printf("변수: da1=%30.25lf\n", da1);	// double - 15자리 유효숫자

printf("변수: da2=%lf\n", da2);

printf("FLT_MIN = %e, FLT_MAX=%e\n", FLT_MIN, FLT_MAX);

printf("DBL_MIN = %e, DBL_MAX=%e\n", DBL_MIN, DBL_MAX);

return 0;

}

- [부록 5] p.680: 부동 소숫점 형식 (floating point format)

⇒ 실수를 저장하는 몇가지 서로 다른 방식들이 고안되었음

e.g., 부호 부분 - 정수와 마찬가지로 양수 0, 음수 1

지수 부분 - 지수를 ‘2진수’로 나타냄,	// 코딩할 수의 범위 결정

소수 부분 - 유효 숫자 (23 bits)	// 코딩할 수의 정밀도 결정

(-9.25)10 = (-1001.01)2 = (-.100101)2×24

1       8                 23

1	00000100	1001010000000……… 0

e.g., IBM 3000/4300 series

⇒ 부호 부분 - 양수 0, 음수 1

지수 부분 - 지수를 '16진수'로 나타냄

소수 부분 - 유효 숫자 (24 bits)

1       7                   24

0	1000010	101100110000010……… 0

부호 - 양수

지수 부분	(1111111=127)

1×26 + 1×21 = 66   ⇒ 1666-64

// 기준점: 가장 작은 수 160-64, 가장 큰 수 16127-64

소수 부분

1×(2)-1 +1×(2)-3 +1×(2)-4 +1×(2)-7 +1×(2)-8 +1×(2)-14

⇒	1×(1/2)1 +1×(1/2)3 +1×(1/2)4 +1×(1/2)7 +1×(1/2)8 +1×(1/2)14

⇒ +[1×(1/2)1 +1×(1/2)3 +1×(1/2)4 +1×(1/2)7 +1×(1/2)8 +1×(1/2)14]1666-64

= 179.015625

⇒ [179.01561737060546875, 179.01563262939453125]의 실수를 표현하는데 사용

Why?

이보다 한단계 큰 수 표현 (+1)

0	1000010	101100110000010……… 1

= 179.0156402587890625

이보다 한단계 작은 수 표현 (-1)

0	1000010	101100110000001111 … 1

= 179.0156097412109375

- 표준화: Wikipedia - single precision (IEEE 754)

n = (-1)s × 1.(m‧2-23) × 2x-127

where, s: the sign bit,

x: the exponent, 수의 범위 결정

// 지수(exponent)의 기준점: 2-127

// 기준점: 가장 작은 수 20-127, 가장 큰 수 2255-127

m: the significant in base 10, 수의 정밀도 결정

// 맨 앞자리에 1이 오게끔 encoding함, 1bit 절약

// 2-23은 m의 23번째 자리에 소숫점을 위치시킴

e.g,, real.c

(from http://en.wikipedia.org/wiki/IEEE_754-1985)

Single-precision 32-bit: 'Decoding' IEEE 754 → decimal

The number 0.15625 represented as a single-precision IEEE 754-1985 floating-point number. See text for explanation.

A single-precision binary floating-point number is stored in 32 bits, as shown at right.

If the number is normalized (the most common case), it has this value:

where:

sign = the sign bit. (0 makes the number positive or zero; 1 makes it negative.)

expo = the 8-bit number stored in the exponent field. expo = the true exponent + 127. (See above for why.)

fraction = the 23 bits of the fraction field.

In the example,

the sign is 0, so the number is positive;

expo is 124, so the true exponent is 124–127 =–3;

and fraction is .01;

(i,e., m = 010 0000 0000 0000 0000 0000      // 23 bits

m․2-23 = .010 0000 0000 0000 0000)

So, the represented number is:

(Subscripts indicate the base of the number: base 2 or base 10.)

A more complex example: 'Encoding' decimal → IEEE 754

Bit values for the IEEE 754 32bit float -118.625

The decimal number −118.625 is encoded using the IEEE 754 system as follows:

The sign, the exponent, and the fraction are extracted from the original number. Because the number is negative, the sign bit is "1".

Next, the number (without the sign; i.e., unsigned, no two's complement) is converted to binary notation, giving 1110110.101. The 101 after the binary point has the value 0.625 because it is the sum of:

(2−1) × 1, from the first bit after the binary point

(2−2) × 0, from the second bit

(2−3) × 1, from the third bit.

That binary number is then normalized; that is, the binary point is moved left, leaving only a 1 to its left. The number of places it is moved gives the (power of two) exponent: 1110110.101 becomes 1.110110101 × 26. After this process, the first binary digit is always a 1, so it need not be included in the encoding.

The rest is the part to the right of the binary point, which is then padded with zeros on the right to make 23 bits in all, which becomes the significand bits in the encoding: That is, 11011010100000000000000.

The exponent is 6. This is encoded by converting it to binary and biasing it (so the most negative encodable exponent is 0, and all exponents are non-negative binary numbers). For the 32-bit IEEE 754 format, the bias is +127 and so 6 + 127 = 133. In binary, this is encoded as 10000101.

▸실수형: 무리수의 경우

#include <stdio.h>

int main(){

float x=1.1;

float sumx=0.0;

int i;

for(i=0; i<20; i++){

sumx=sumx+x;

printf("sumx=%f\n", sumx);

}

return 0;

}

기초 수학 모듈 - 수의 체계

• [Chap 04] p.184 - p.202

• 진수 연산

• 진법 변환

• 보수 연산