Information Storage
컴퓨터에서 숫자를 표현하는 대표적인 3가지 방법:
- Unsigned numbers, 0보다 큰 정수를 나타날때 유용
- Two's complement, 0보다 크거나 작은 정수를 나타날때 유용
- Floating-point number, 2진법으로 실수를 나타내는 방법
16 진수 notation
A 에서 10...
만약 binary 가 4자리로 떨어지지 않는다면 좌측에 0을 padding 함.
x = 2^n 이라고 할 때, x는 n개의 0이 뒤에 있는 1.
-> 2^1 = 10, 2^2 = 100 ...
이러한 x를 16진수로 표현할 때는 n을 i+4j로 만든 후,
16진수의 첫번째 자리를 2^i, 뒤 0의 갯수를 j로 변환시킨다.
2^11 = 2^3+4*2
첫째자리: 2^3
0의갯수: 2개 -> 0x800
decimal <-> hexadecimal 변환
10진수에서 16진수로 변환하기 위해서는 10진수 x값에 16을 반복적으로 나누어야한다.
314,156 = (16^4 4) + (16^3 12) + (16^2 11) + (16^1 2) + 12
= 262144 + 49152 + 2816 + 32 + 12 = 314,156
Byte Ordering
w-bit integer representation, x_w-1, x_w-2.... x_0
w가 8의 배수라면 8 bit 씩 나눌 수 있다.
[x_w-1, ... x_w-8] .... [x_7, ... x_0]
most significant byte least significant byte
거의 모든 machine 에서는 낮은 주소부터 높은 주소 순으로 데이터를 저장한다.
이렇듯 LSB 를 먼저 저장하는 방식을 little endian,
MSB 를 먼저 저장하는 방식을 big endian 이라고 한다.
Integer Representation
나타낼 수 있는 음수의 범위가 양수의 범위보다 넓다.
short -32,768 ~ 32,767
int -2,147,483,648 ~ 2,147,483,647
Unsigned Encodings
Function B2Uw is a bijection(일대일로 대응).
Two's complement Encoding; Signed number
most significant bit of the word 가 negative weight 를 표현
이를 sign bit 라고 함. 1이면 negative, 0이면 non-negative(positive)
TMin_w = -2^w-1 (w=4, 1000 is minimum value)
TMax_w = 2^w−1 − 1 (w=4, 0111 is maximum value)
unsigned 와 마찬가지로 bijection 이다
이렇듯 unsigned type 의 range 는 symmetric 하지만 signed type 의 range 는 assmmetric 한 이유는 sign bit 의 사용 때문이다.
word size 가 16 bit 일때,
-1 = 0xFFFF
0 = 0x0000
Signed 와 Unsigned 간의 변환; Casting
signed 음수 값을 unsigned 으로 변환하면 0이 될까?
signed 범위 이상의 unsigned 값을 signed 으로 변환하면 TMax가 될까?
-> numeric이 아닌 bit-level에서 계산된다. 즉, bit 값은 보존하되, interpret 하는 방법이 바뀐다.
short int v = -12345, unsigned short uv = (unsigned short)v
uv = 53191
53191 + 12345 = 65536 = 2^16 와 같은 특성을 가진다.
즉,
T2U_32(−1) = 4,294,967,295,
U2T_32(4,294,967,295) = −1.
Implicit casting
signed 와 unsigned 값간의 비교/연산 시 implicit 한 casting이 이루어져 nonintuitive한 결과를 내놓는다.
ex)
signed -1 와 unsigned 0 을 빅하면 -1이 더크다고 결과값이 나옴.
이렇게 되는 이유는 signed -1 가 unsigned로 변환되면서 양수 4,294,967,295 가 되기 때문이다. 4,294,967,295 > 0
이러한 implicit casting 에 의한 오류를 방지하는 가장 좋은 방법은 unsigned type 을 사용하지 않는것이다.
Expanding Bit representation; casting bt different word size
작은 word size에서 큰 word size로 convert는 흔함.
unsigned 에서는 zero extension을 수행, 즉 확장된 bit수 만큼 0을 더함
1111 -> 00001111
signed 에서는 sign extension 을 수행, 즉 확장된 bit 수만큼 sign bit를 더함.
1111 -> 11111111 = -1
0111 -> 00001111 = 7
size와 type 모두 변환 시, size부터 변환 후 type 을 변환한다.
Integer Arithmetic
Unsigned Addition & Negation
word 가 4 bit 라고 할때,
9 + 12 = 5
1001 + 1100 = 1"1001" 유효 범위를 초과하는 bit는 truncate.
이러한 overflow 현상때문에 취약점이 발견되기도 한다.
word 가 4 bit 라고 할때,
x = 3, -x = 13
Two's complement Addition & Negation
-> 이렇듯 unsigned 이나 signed 모두 같은 연산 instruction 을 사용한다는것을 알 수 있음.
1 - 2 = 1 + (-2) 임을 이용해서 더하기의 법칙을 적용함.
Unsigned multiplication
더하기와 마찬가지로, 곱하고 초과되는 bit 수만큼 truncating 함.
Signed mulitplication
unsigned 곱셈과 동일하지만, u2t 과정이 추가됨.
->Bit-level equivalence of unsigend and two's complment mulitplication
Multiplying by Powers of 2/Constants
곱셈은 다른 연산에 비해 10배에 가까운 clock을 소모한다.
->상수 곱셈은 shifiting 이나 addition 으로 대체하여 최적화를 수행함.
ex) Power of 2 의 곱셈
x2^k = k갯수만큼의 0이 추가된다.
-> 1101 1000 = 1101000
즉, k 만큼 left shifting 을 수행하면 된다.
binary 에서 1이 연속으로 나오는 경우, 이를 활용할 수 있다.
ex) word 가 8비트일때,
14 = 00001110
두가지 방법
1. x 14 = (x<<3) + (x<<2) + (x<<1)
2. x 14 = (x<<4) - (x<<1)
Dividing by Powers of 2/Constants
Unsigned number 를 나눌때, 다음과 같이 right shifting 을 수행한다.
Round toward zero 규칙에 맞게 반내림한 10진수 결과값을 도출해낸다.
Two's complement number 를 나눌때도 right shifting 을 수행하고, Round toward zero 규칙에 맞게 반내림을 수행해야하지만, 음수값을 나눈 후에 반내림을 적용하면 toward zero 가 아니게 된다. 따라서 이런 경우에는 bias 값을 더한 후, 반내림을 적용하면 된다.
-12,340 + 15 = -12,325
-12,325 / 16 = -770.3125,
-770.3125 반내림 -> -771
즉, 다음과 같은 특징을 이용한것이다.
Floating-Point number
Fractional Binary numbers
분수값을 가지는 binary numbers
decimal 표기법은 "."소수점을 기준으로 각 digit의 weighting 이 달라진다.
left of "." = nonnegative power of 10,
right of "." = negative power of 10
-> 12.34 = 1 10^1 + 2 10^0 + 3 10^-1 + 4 10^-2
binary에서는 "."을 binary point 라고 한다.
여기서도 마찬가지로 "."을 기준으로 weighting 이 달라진다.
left of "." = nonnegative power of 2
right of "." = negative power of 2
-> 101.11 = 1 2^2 + 0 2^1 + 1 2^0 + 1 2^-1 + 1 * 2^-2
binary point 를 left shifting 한다는것 = dividing by 2
binary point 를 right shifting 한다는것 = multiplying by 2
ex) 101.11 -> 10.111 ; 2 나누어짐
101.11 -> 1011.1 ; 2 곱해짐
이러한 fractional binary number 는 x * 2^y 값만 표현할 수 있다.
마치 decimal 표기법에서 1/3 5/7 등이 표현 불가능한것과 같은 이치..따라서 approximation을 통해 가장 근접한 값을 사용한다.
ex) 1/5 는 binary 로 표현 불가능하다. 따라서..
->
IEEE Floating-point Representation
V = (−1)^s × M × 2^E 로 표현한다.
이유: 5 x 2^100 을 10진수로 표현하기에는 너무 길어져서 x * 2^y 의 형태로 표현하는 것
s: 부호(sign) 결정
M: Fractional Binary Number
E: 가중치
exp bit 는 E 인코딩
frac bit 는 M 인코딩
exp 값에 따른 3가지의 경우.
Case 1. Normalized Value
exp값이 all zeros 거나 all ones 이 아닐때
이때 exp필드는 biased signed integer 와 같은 방법으로 해석된다.
즉, 2^8 = 256 이다. 그러므로 중간값인 127을 기준으로 음수와 양수로 나뉜다.
따라서 이 중간값, bias 를 자동으로 더한 값을 exp field 에 저장한다.
ex) 8 bit bias = 2^8-1 = 127.
exp 가 7이라면, 127+7 = 134 의 2진수 표현이 exp field 에 저장된다.
exp 가 -7 이라면, 127-7 = 120 의 2진수 표현이 exp field 에 저장된다.
따라서 exponent value E = e - Bias
(e is unsigned integer representation)
frac 부분은 fractional binary number 처럼 해석되지만,
M = 1 + . (implied leading 1 representation)
f 앞에 항상 1.0이 추가된다.
fractional binary number 에서 1.0 을 추가로 표현할 필요가 사라진다. 한비트라도 더표현가능, 오차범위 줄어듦.
이는 E값을 수정해서 언제든지 크기를 변경할 수 있다는 특성을 활용한것이다.
Case 2. Denormalized Value
exp가 all zeros 일때, 해당값이 denormalized value 라는것을 나타냄.
이때, E = 1 - Bias 로 해석되고, M = . (implied leading 1 없이) 로 해석된다.
이러한 Denormalized Value 의 목적은 다음과 같다.
1. Floating point number 는 그 특성상 M >= 1 의 값만 가지는데, 이를 파훼하여 0.0 이라는 값을 표현하기 위해서 특별한 경우를 설정해둔것.
2. Gradual undeflow 라는 특징을 제공
Case 3. Special Value
exp가 all ones 이고, M 이 0이면 ∞을 의미함.
M 이 0이 아니면 NaN, No a Number
√-1 이나 -∞, +∞ 을 나타냄
몇가지 대표적인 표현.
* +0.0 = all zeros
* smallest positive denormalized value = LSB 1 & others zero
* largest denormalized value = exp zeros, f all ones
* 1.0 = exp of 127, f all zeros Rounding
floating number 는 2^n 이 아닌 수는 모두 근사치로 표현해야하마. 가장 가까운 값을 찾는 task를 Rounding 이라고 함.
- Round-to-Even
가장 가까운 수로 반올/내림 하지만, 0.5의 경우 짝수에 가까운 쪽으로 반올/내림한다.
ex) 1.5 -> 2, 2.5 -> 2 - Round-toward-Zero
양수는 반내림, 음수는 반올림 |x^| <= |x| 가 되게끔 만듦. - Round-down/up
무조건 내림/올림
이 모드를 사용하면 통계적 편향(statistical bias)를 초래할 수 있다.
fractional binary number 에 이와 같은 Rounding 모드가 적용된다.
XXX.YYY100 와 같은 bit pattern만이 halfway 를 나타낸다.
ex) 10.00011 -> 10.00, 10.00110 -> 10.01
얘네는 halfway가 아님
10.11100 -> 11.00, 10.10100 -> 10.10
halfway 이므로 Round-to-even 이 적용(0이 짝수, 1이 홀수로 적용됨)
