-
[CS:APP/시스템 프로그래밍]DataLab bits.c 풀이Programming/CS:APP 2024. 3. 11. 07:51
CMU CSAPP (Computer Systems: A Programmers Perspective, 컴퓨터 시스템) Data Lab 과제 Solution 및 해설입니다.
비트 연산과 2의 보수 체계의 이해를 바탕으로 기본 논리 연산부터 부동소수점 처리까지 다양한 연산을 구현하는 과제입니다.
과제 문항별 설명과 해결 과정, 최적화 방법을 다루고 있습니다.Intro
CMU CSAPP 홈페이지 에서 과제 다운로드가 가능하다.
과제를 받으려면 CSAPP 계정이 필요하다. 수강 인증을 해야 발급이 가능하다.
나처럼 혼자 책 사서 공부하는 경우에는 계정 발급이 불가능하다. 이럴 땐 대신 Self-Study Handout 버전을 받으면 된다.Self-Study Handout 링크가 클릭이 안되는 경우
링크를 클릭해도 아무런 반응이 없을 수 있다.
윈도우는 오른쪽 마우스 다른 이름으로 링크 저장. 혹은 리눅스라면 그냥 webget 해주면 된다.
wget http://csapp.cs.cmu.edu/3e/datalab-handout.tarfatal error: bits/libc-header-start.h: No such file or directory 오류
32비트 컴파일용 라이브러리가 없어서 생기는 문제이다.
다음과 같이 받아준다 (Ubuntu)
sudo apt-get install gcc-multilibINTEGER CODING: 정수 비트 연산 구현
bitXor
//1 /* * bitXor - x^y using only ~ and & * Example: bitXor(4, 5) = 1 * Legal ops: ~ & * Max ops: 14 * Rating: 1 */&와~만 사용해 XOR 연산을 구현해야 한다.XOR은 $(A-B) \cup (B-A)$ 로 표현가능하다. 문제에서 or 연산이 사용불가하니 이를 and 연산으로 바꿔줘야 한다.
중학교? 때 배웠던 드모르간의 법칙을 사용하면 되겠다.
$(A-B) \cup (B-A)$에 드모르간을 취해준다.
$((A \cap B^{c}) \cap (B \cap A^{c}))^{c}$코드로 구현해보자.
int bitXor(int x, int y) { return ~(~(x & ~y) & ~(~x & y)); }정답이다. 근데 한 가지,
~가 너무 많다. 더 깔끔한 방법은 없을까?XOR 을 $(A \cup B) - (A \cap B)$ 라고 보자.
$(A \cup B)$ 에 드모르간을 취하는 것으로 아래와 같이 표현할 수 있다.$(A^{c} \cap B^{c})^{c} - (A \cap B)$
최종 코드는 다음과 같다.
int bitXor(int x, int y) { return ~(~x & ~y) & ~(x & y); }
Tmin
/* * tmin - return minimum two's complement integer * Legal ops: ! ~ & ^ | + << >> * Max ops: 4 * Rating: 1 */2의 보수 체계에서 가장 작은 정수를 반환해야 한다.
shift 연산으로 간단하게 구할 수 있다.
int tmin(void) { return (1 << 31); }
isTmax
/* * isTmax - returns 1 if x is the maximum, two's complement number, * and 0 otherwise * Legal ops: ! ~ & ^ | + * Max ops: 10 * Rating: 1 */이전 문제와 반대로 이번엔 2의 보수 체계에서 가장 큰 정수를 판별해야 한다.
(1 << 31) - 1로 간편하게Tmax를 구하면 참 좋겠다만, 조건 상 shift 연산자를 사용할 수 없다.또, 결과는 0 또는 1, boolean으로 반환해야 한다. 아래 코드처럼 말이다.
int isTmax(int x) { return (x == Tmax); }물론 비교 연산
==역시 사용할 수 없다.
없으면 직접 만들어야 한다.입력값이
Tmax면 1을, 아니면 0을 반환하는 연산을 고안해야한다.
혹은 입력값이Tmax면 0을, 아니면 0이 아닌 값을 반환하는 연산에 논리 부정 연산자!를 더해줘도 되겠다.아무래도 후자가 더 편할 듯 하다.
Tmax를 0으로 만드는 데 활용가능한Tmax만의 특수한 성질이 따로 있을까?
생각해보다 다음을 발견했다.Tmax는 1을 더했을 때 모든 자리의 비트가 반전된다.
Tmax에 1을 더하면, 부호를 제외한 모든 비트에서 자리 올림이 발생한다.
모든 1이 0이 되고, 0이었던 부호 비트는 1이 된다.다른 숫자는 자릿수가 충분하지 않다. 1을 더해도 반전되지 않는 비트가 있을 수 밖에 없다.
사실
Tmax말고도 이런 성질을 갖는 수가 하나 더 있다. 바로-1이다.0xFFFFFFFF에 1을 더하면 0이다. 모든 자리의 비트가 반전된다.정리하면, x가
Tmax거나-1일 때x + 1은~x와 같다. x가 다른 값일때는 성립하지 않는다.두 값에 xor 연산을 취하면
Tmax와-1만 0이 된다.
설명의 편의를 위해 연산(x + 1) ^ ~x를f(x)라고 하자.f(Tmax) == 0,f(-1) == 0이다.
x가 다른 값일 때는f(x) != 0이다.-1이라는 예외가 있는 건 아쉽지만, 수많은 x값 중에서 -1과 Tmax만 0이 되는 연산을 발견한 건 나름 중요한 성과다.
여기서 -1만 따로 걸러낼 수만 있다면 답을 낼 수 있다.
즉,
g(-1) != 0이면서g(Tmax) == 0인 연산g(x)를 하나 찾으면 된다.
이때!(f(x) | g(x))가 해답이 된다.~(-1) == 0이니까 간단하게!(~x)를g(x)로 삼으면 된다.int isTmax(int x) { return !(((x + 1) ^ (~x)) | !(~x)); }정답 내고 다른 문제 풀다가 문득 든 생각.
자기 자신이 덧셈의 역원인 수는 Tmin 과 0 뿐이다
이들은 각각~Tmax,~(-1)이기도 하다.따라서 모든 x에 대해
~x + ~x == 0인 x는 Tmax와 -1 뿐이다.이를 활용하면 산식을 더 간소화 할 수 있다.
int isTmax(int x) { int nx = ~x; return !((nx + nx) | !(nx)); }
allOddBits
/* * allOddBits - return 1 if all odd-numbered bits in word set to 1 * where bits are numbered from 0 (least significant) to 31 (most significant) * Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 12 * Rating: 2 */홀수 비트가 모두 켜져 있으면 1을 반환해야 한다.
모든 홀수 비트만 1인 비트마스크
0xAAAAAAAA에x = x & 0xAAAAAAAA를 취해주면 x의 모든 짝수 번째 비트가 0이 된다.이후
x ^ 0xAAAAAAAA을 해준다.
x의 모든 홀수 비트가 1이면x == 0xAAAAAAAA이고0xAAAAAAAA ^ 0xAAAAAAAA == 0이 된다.
1이 아닌 홀수 비트가 있다면 0이 아니게 되니 논리부정 연산!를 취해주면 정답이다.한편 문제에서 8비트 이상의 상수를 사용하는 게 금지되어 있다.
귀찮지만 아래처럼0xAA를 조합해서 마스크를 만들어야 한다.int mask = 0xAA + (0xAA << 8) + (0xAA << 16) + (0xAA << 24);혹은 다음 방법으로 연산 수를 줄일 수도 있다.
int mask = 0xAA + (0xAA << 8); mask += mask << 16;최종 코드는 다음과 같다.
int allOddBits(int x) { /* 0xAAAAAAAA: Mask for all odd bits */ int mask = 0xAA + (0xAA << 8); mask += mask << 16; return !((x & mask) ^ mask); }
negate
/* * negate - return -x * Example: negate(1) = -1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 5 * Rating: 2 */이거는 문제 풀다 보니 쓸 일이 많아 자동으로 외워졌다. 외워주자.
int negate(int x) { return (~x + 1); }
isAsciiDigit
/* * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9') * Example: isAsciiDigit(0x35) = 1. * isAsciiDigit(0x3a) = 0. * isAsciiDigit(0x05) = 0. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 3 */0011 0000에서0011 1001까지 걸려줘야 한다. (1로 만들어줘야 한다)0011 0000에서0011 0111까지 값은 전부 앞부분,0011 0***이 같다. 뒤 3자리는 굳이 볼 필요가 없다.볼 필요가 없으니 아예 없애버린다.
우측 쉬프트 후 XOR을 취하면 정확히0x30에서0x37까지의 값만 0이 된다./* 0x06: 0b00110 */ !((x >> 3) ^ 0x06)사실 shift의 순서는 별로 중요치 않다.
0x06보다0x30이 연산의 의도를 더 잘 드러낸다.
따라서 다음과 같이 바꿔준다.!(x ^ 0x30) >> 3)0011 1000에서0011 1001의 범위 역시 앞에서0011 100*까지만 같으면 뒤 한 자리는 상관이 없다.!(x ^ 0x38) >> 1)둘 중 하나라도 값이 1이라면 범위에 해당하는 값이다.
bitwise or로 이어준다.int isAsciiDigit(int x) { /* (x ^ 0x30) >> 3 == 0 iff 0x30 <= x <= 0x37 (2^3 integers) * (x ^ 0x38) >> 1 == 0 iff 0x38 <= x <= 0x39 (2^1 integers) */ return !((x ^ 0x30) >> 3) | !((x ^ 0x38) >> 1); }
conditional
/* * conditional - same as x ? y : z * Example: conditional(2,4,5) = 4 * Legal ops: ! ~ & ^ | + << >> * Max ops: 16 * Rating: 3 */if문 없이 조건식을 구현해야한다.
조건에 따라 다른 값을 어떻게 반환할 수 있을까?
조건에 맞는 값에 1을, 맞지 않는 값에 0을 곱해주면 될 것 같다.
(x == 0) * y + (x != 0) * z;물론 등호와 곱하기는 사용할 수 없다.
등호는 사용할 수 없지만, 논리 부정
!는 사용 가능하다.!(x)는 x가 참이면 0, 거짓이면 1로 만들어준다.곱하기 대신 사용할만한 연산자로는 bitwise and
&이 있다. 아래와 같은 구현을 생각해볼 수 있다.
x가 참이면(0xFFFFFFFF & y) | (0x00000000 & z)-> y값 반환
x가 거짓이면(0x00000000 & y) | (0xFFFFFFFF & z)-> z값 반환즉 연산
f(x)가
x가 참일때(!(x) == 0)f(x) == 0xFFFFFFFF
x가 거짓일때(!(x) == 1)f(x) == 0x00000000
라고 하면(f(x) & y) | (~f(x) & z)가 정답이다.대응 관계를 보면 바로 직관적으로
!(x) - 1이 떠오른다.물론
-연산은 사용할 수 없다.
대신 negation과 덧셈 역원의 대응관계-x == ~x + 1-x == ~(x - 1)를 이용해 뺌셈을 덧셈으로 전환 가능하다.!(x) + (~0)를 쓰면 되겠다. 같은 값을 여러번 사용하니 변수로 만들어주자.
변수명은 mask로 하자.최종
int conditional(int x, int y, int z) { /* x == 0: mask = 0x00000000 * x != 0: mask = 0xffffffff * Note that !(x) + (~0) == !(x) - 1 */ int mask = !(x) + (~0x00); return (y & mask) | (z & ~mask); }
isLessOrEqual
/* * isLessOrEqual - if x <= y then return 1, else return 0 * Example: isLessOrEqual(4,5) = 1. * Legal ops: ! ~ & ^ | + << >> * Max ops: 24 * Rating: 3 */대소비교를 구현해야한다.
x <= y대신0 <= y - x를 판별하면 더 편할듯 한데, 연산 과정에서 오버플로우가 발생할 수 있어 완벽히 대응되지 않는다.단,
y - x연산은 서로 부호가 다를 때만 오버플로우 가능성이 있다.
또, y와 x의 부호가 다르다면, 굳이y - x의 부호 (0 보다 크거나 같은지)를 확인할 필요가 없다.
자명하게도, y가 양수면 y가 큰 값이고, y가 음수면 y가 작은 값이겠다.따라서 정답은 이전 문제 conditional과 유사한 다음과 같은 구조가 되겠다.
(x_sign != y_sign) * (y >= 0) + (x_sign == y_sign) * (y - x >= 0);이전과 같이
x_sign != y_sign을 위한 마스크를 만들어 준다.x ^ y의 부호를 생각해보자.
x와 y의 부호가 서로 다르면 1, 같으면 0이 된다.부호 부분을 우측 shift로 당겨와 적절한 마스크를 만드는 게 가능하다.
부호가 다르면0xFFFFFFFF, 부호가 같으면0x00000000이 된다. signed int에 arithmatic shift를 수행하기 때문이다./* mask: 0xFFFFFFFF if x_sign != y_sign * mask: 0x00000000 if x_sign == y_sign */ int mask = (x ^ y) >> 31;마스크를 만들었으니 조건에 따라 y 혹은 y - x 값을 가져올 수 있다.
우리의 관심사는 값 전체가 아닌 부호 값이다. 우측 shift로 부호를 가져온다.
역시 y가 더 작다면(y 혹은 y - x 가 음수)0xFFFFFFFFy가 더 크거나 같다면0x00000000이 된다.여기에 1을 더해주면 적합한 반환 값이 만들어진다.
/* res: 0x00000000 if x <= y (positive sign shifted) * res: 0xFFFFFFFF if x > y (negative sign shifted) */ int res = ((mask & y) | (~mask & (y - x))) >> 31; return res + 1;물론
-연산은 제한되어 있기에+로 바꿔줘야 한다. negation 문제에서 했던 부분이라 어렵지 않다.또한 값의 부호만 판단하면 되기 때문에 마스크를 굳이 shift 해줄 필요가 없다.
부호 부분만 적절하게&되기만 하면 되기 때문이다.그렇게 작성한 최종 코드
int isLessOrEqual(int x, int y) { int mask = x ^ y; /* If x and y have different signs, then sign of y is relevant * else, sign of y - x (y + ~x + 1) is relevant * if sign is positive, then x <= y * right shift to set value to 0x00 (and thus 1) */ return 1 + (((mask & y) | (~mask & (y + ~x + 1))) >> 31); }
logicalNeg
/* * logicalNeg - implement the ! operator, using all of * the legal operators except ! * Examples: logicalNeg(3) = 0, logicalNeg(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */논리 부정을 구현해야 한다.
input이 0일 때만 걸러내야 한다. 0의 특성을 생각해보자.
이전에 자기 자신이 덧셈의 역원인 숫자는 Tmin 과 0밖에 없다 는 점을 언급한 바 있다.
이를 활용해 과거 isTmax 문제처럼
Tmin과 0 중에서Tmin만 걸러내면 되지 않을까?
라는 생각에 아래와 같은 코드를 작성했다.return !((x + x) | x);틀렸다.
당연하게도 논리 부정을 구현하는 문제기 때문에
!연산을 사용해선 안된다.논리 부정 연산 없이 값을 0 또는 1로 제한할 수 있어야 한다.
생각해보면 바로 이전 문제, isLessOrEqaul에서 논리 부정 없이 0 또는 1로 결과를 반환했었다.
부호를 우측 shift 연산으로 쭉 가져와 1을 더하는 방식으로 구현했었다. 여기서 아이디어를 빌려오자.자기 자신이 덧셈의 역원인 숫자 Tmin과 0 중, 0만 부호가 0이다
이게 무슨 소리냐, x와 -x의 부호를
(x_sign, -x_sign)이라고 하자. 다음 4가지 케이스가 있다.- 0 이 아닌 양수:
(0, 1) - Tmin이 아닌 음수:
(1, 0) - Tmin:
(1, 1) - 0:
(0, 0)
즉
(x | -x)가 양수인 수는 0 밖에 없다.
이를 활용하면 답안 작성이 가능하다.int logicalNeg(int x) { /* Only 0 has positive sign for both x and -x */ return ((x | (~x + 1)) >> 31) + 1; }
howManyBits
/* howManyBits - return the minimum number of bits required to represent x in * two's complement * Examples: howManyBits(12) = 5 * howManyBits(298) = 10 * howManyBits(-5) = 4 * howManyBits(0) = 1 * howManyBits(-1) = 1 * howManyBits(0x80000000) = 32 * Legal ops: ! ~ & ^ | + << >> * Max ops: 90 * Rating: 4 */숫자 표현에 필요한 비트 수를 세는 문제.
이 문제에 가장 시간을 많이 썻다.먼저 구해야 하는 "필요한" 비트 수라는 게 정확히 뭔지 생각해보자.
16비트 숫자0000 0001 1011 1111은01 1011 1111로도 표현이 가능하다. 따라서 필요한 비트는 10개이다.
16비트 음수1111 1111 1111 1001은1001로도 표현이 가능하다. 따라서 필요한 비트는 4개이다.양수는 가장 왼쪽 1의 위치를 통해, 음수는 가장 왼쪽 0의 위치를 통해 필요한 비트 수를 가늠할 수 있다.
가장 왼쪽의 1/0의 위치 + 부호 표현용 비트 1개가 필요한 비트 수가 된다.
음수는 0, 양수는 1을 세야 한다는 게 다소 불편하다.
x 가 n개 비트로 표현 가능하면 ~x 역시 n개 비트로 표현 가능하다. 따라서 음수일 경우 뒤집어주기로 한다.x >> 31과 xor을 취하여 부호에 따라 뒤집는 게 가능하다.x ^= x >> 31;이제 비트 수를 구해야 한다.
무식한? 방법
이제 가장 왼쪽 1의 위치를 구해야 한다.
문제는 가장 왼쪽 여부를 어떻게 확인해야 하는지, '위치' 라는 개념을 어떻게 판별해야 하는지 판단이 잘 서지 않았다.따라서 아예 판별하지 않는 방식을 고안했다.
shift 연산을 통해 가장 왼쪽 1(이하 MSB) 보다 우측에 있는 비트를 모두 1로 만드는 방식이다.
x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;x가
0000 0001 1010 1011라면0000 0001 1111 1111이 된다.
이제 1의 개수가 곧 1의 위치를 나타내므로 개수를 세어주면 된다.문제는 1의 개수를 세는 것도 쉽지 않다는 점이다. 우리는 반복문을 쓸 수 없다.
cnt = !!(x); cnt += !!(x >> 1); cnt += !!(x >> 2); cnt += !!(x >> 3); cnt += !!(x >> 4); cnt += !!(x >> 5); /* ... */위와 같이 하나씩 세다가는 요구한 Max ops를 넘어가게 된다.
연산 수를 줄이기 위해 1이 아닌 0의 개수를 우회적으로 세더라도 마찬가지이다.각 자리를 셀 때 3회 이상 연산을 수행하면 Max ops 초과이다.
더 효율적인 세는 방식을 찾아야 한다.그래서 고안해 낸 건...
두 칸 씩 세는 방법이다.우스꽝스럽지만, 조건문 없이 가장 간단하게 셀 수 있는 단위가 절묘하게도 2개 비트라는 점을 발견했다.
x가
0001 1111 1111 1111이라고 하자.홀수 번째 비트만 가져온 값
0000 1010 1010 1010과 가장 왼쪽 비트(x >> 1) ^ x == 0001 0000 0000 0000.
두 값을 bitwise|한 결과는0001 1010 1010 1010이다.비트 두개의 값이 곧 기존에 있던 1의 개수와 같다!
mask = 0xAA + (0xAA << 8); mask += mask << 16; x = (x & mask) | ((x >> 1) ^ x ); cnt = x & 0x03; cnt += (x >> 2) & 0x03; cnt += (x >> 4) & 0x03; cnt += (x >> 6) & 0x03; cnt += (x >> 8) & 0x03; cnt += (x >> 10) & 0x03; cnt += (x >> 12) & 0x03; cnt += (x >> 14) & 0x03; cnt += (x >> 16) & 0x03; /* .... */ return cnt + 1;이걸로 간신히 Maxops 제한을 벗어났다.
이분 탐색
두 칸 씩 세기 위해 같은 줄을 15번 복붙하며 답안을 작성했다. 범죄를 저지르는 듯한 기분이 들었다.
더 효율적인 방식을 생각해 보기로 했다. 분명 이게 모범 답안이 아닐 것이다.이분 탐색과 같은 방식으로 구현해보면 좋겠다.
잠깐 문제 조건을 무시하고, If 문을 사용해서 이진 탐색을 한다고 생각해보자.먼저 x가 절반(0xFFFF)보다 크다면 x는 16자리 이상 숫자가 된다.
16을 count에 추가하고 x를 16만큼 오른쪽으로 shift 해준다.
아닐 경우 그냥 두면 된다.그 다음 (shift 해준) x가 1/4(0xFF)보다 크다면 (shift 해 준) x는 8자리 이상 숫자이다.
8을 count에 추가하고 x를 8만큼 오른쪽으로 shift 해준다.이렇게 count를 누적 해가며 조건에 따라 x를 shift 하면 6번 만에 셀 수 있다.
int shift, cnt; cnt = 0; if (x > 0xFFFF) { x >> 16; cnt += 16; } else { x >> 0; cnt += 0; } if (x > 0xFF) { x >> 8; cnt += 8; } else { x >> 0; cnt += 0; } /* ... */ return cnt + 1;그럼 이제
x > 0xFFFF는 어떻게 구현할까?앞에서 isAsciiDigit 에서 사용한 방법을 재활용해보자.
!((x ^ 0x30) >> 3)을 통해0x30이상인 수 8개를 1로 만들 수 있었다.응용하면,
x > 0xFFFF == x >= 0x00010000x >= 0x00010000 == !((x ^ 0x00010000) >> 16) == !((x >> 16) ^ 0x0001)) == !!(x >> 16)이 된다.이제
!!(x >> 16)에 16을 곱한 값은 x 가0xFFFF보다 크다면 16, 작다면 0인 값이 된다.
$x \times 2^{n}$ 는x << n임을 이용하면 쉽게 곱할 수 있다.같은 방식을 16, 8, 4, 2, 1, 0 이 되도록 반복한다.
int cnt; int shift; /* Flip if negative */ x ^= x >> 31; cnt = 0; shift = !!(x >> 16) << 4; x >>= shift; cnt += shift; shift = !!(x >> 8) << 3; x >>= shift; cnt += shift; shift = !!(x >> 4) << 2; x >>= shift; cnt += shift; shift = !!(x >> 2) << 1; x >>= shift; cnt += shift; shift = !!(x >> 1); x >>= shift; cnt += shift; shift = !!x; x >>= shift; cnt += shift; cnt += 1; return cnt;여기서 연산 수를 조금 더 아낄 수 있다.
shift 변수를 따로 두는 대신, 누적된 count를 연산에 활용하는 방법이다.또 이분 탐색 마지막 길이 1의 구간 확인에 굳이
!!를 쓸 필요가 없다.
어짜피 비트 하나, 1 또는 0이기 때문에 그냥 더해주면 된다.그렇게 작성한 최종 코드
int howManyBits(int x) { int cnt; /* Flip if negative */ x ^= x >> 31; /* Binary search * If left half is nonzero, right half bits are required * thus add its size to count, and check the left-left * else, check the right half * Using current count as a index to shift x the right amount */ cnt = (!!(x >> 16)) << 4; cnt += (!!(x >> (cnt + 8))) << 3; cnt += (!!(x >> (cnt + 4))) << 2; cnt += (!!(x >> (cnt + 2))) << 1; /* Final left and right bit, guaranteed to be 1 or 0 * thus add raw value (instead of boolean) */ cnt += x >> (cnt + 1); cnt += x >> cnt; /* Sign bit */ return cnt + 1; }FLOAT CODING: 부동소수점 연산
floatScale2
/* * floatScale2 - Return bit-level equivalent of expression 2*f for * floating point argument f. * Both the argument and result are passed as unsigned int's, but * they are to be interpreted as the bit-level representation of * single-precision floating point values. * When argument is NaN, return argument * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */부동 소숫점 2배 연산
각 케이스 별로 어떤 작업을 취해줘야 하는지 생각을 해보자.
Speical Value일 경우
- NaN 이면 자기 자신을 반환해야 한다.
- INF 이면 자기 자신을 반환해야 한다. 2를 곱해도 똑같다.
Denormalized Value일 경우
이는 2를 곱한 값이 Denoramlized인지 Normalized인지에 따라 나눠볼 수 있다.두배를 곱해도 여전히 Denormalized인 경우, 가수부(Frac/Mantissa)에 2를 그냥 곱해주면 된다.
즉,uf << 1을 하면 된다.두배를 곱해도 Normalized인 경우, 놀랍게도 역시 그냥 가수부에 2를 곱해주면 된다.
uf << 1을 할 때, 가수 부분의 가장 높은 자리 수(MSB)가 지수 부분을 침범하는 것 아니냐는 생각이 들 수 있다.
지수부0x00과0x01은 곱해지는 지수 자체에는 차이가 없다.
게다가 유효 숫자에 가상의 1의 여부만 달라진다는 점을 생각하면, MSB(0.5)가 2배가 되면서 Normalized 값의 가상의 1이 된다고 볼 수 있겠다.
여기서 왼쪽 쉬프트 연산 시 -부호가 소실되니 다시 붙여줘야 한다.Normalized Value일 경우는 그냥 지수부에 1을 더해주면 된다.
이제 조건문 활용이 가능하다. 간단하게 코드로 옮겨주기만 하면 된다.
unsigned floatScale2(unsigned uf) { unsigned sign = uf & (1 << 31); unsigned exp = (uf ^ sign) >> 23; /* NaN or INF */ if (exp == 0xFF) { return uf; } /* Denormalized */ if (exp == 0) { return (uf << 1) + sign; } /* Normalized */ return uf + (1 << 23); }
floatFloat2Int
/* * floatFloat2Int - Return bit-level equivalent of expression (int) f * for floating point argument f. * Argument is passed as unsigned int, but * it is to be interpreted as the bit-level representation of a * single-precision floating point value. * Anything out of range (including NaN and infinity) should return * 0x80000000u. * Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while * Max ops: 30 * Rating: 4 */정수로 바꿔주기
주어진 부동소수점 수 uf에 대해
지수 부분을 비트 그대로 비 부호형 정수로 취급한 값을 e,
가수 부분을 비트 그대로 비 부호형 정수로 취급한 값을 m 이라고 하자Nomalized Value인 경우 uf 는 다음과 같다.
$$2^{e - 127} \times \frac{m + 2^{23}}{2^{23}} \quad = \quad (m + 2^{23}) \times 2^{e - 127 - 23}$$
정수 변환은 어짜피 Round toward 0 이다.
따라서 $m + 2^{23}$ 을 $e - 127 - 23$ 만큼 좌/우로 shift 해주어 정수로 변환할 수 있다.이 때, 값이 정수 범위 이상으로 커지는 걸 막아야 한다.
가수 부분이 항상 2보다 작기 때문에, $e - 127 < 31$ 이라면 변환 값은 항상 $[-(2^{31} - 1), 2^{31} - 1]$ 안에 들어오게 된다.여기서 $-2^{31}$인 Tmin은 어떻게 처리 하냐고 물을 수 있다.
어짜피 범위 초과시 반환값 자체가 Tmin이라서 고려하지 않아도 된다.이후 변환 값에 부호를 붙여주면 된다.
int sign = uf & (1 << 31); int exp = (uf ^ sign) >> 23; int frac = (uf & 0x00FFFFFF) | (1 << 23); /* bias */ exp -= 127; /* Value out of range (including NaN and infinity) */ if (exp > 31) { return 0x80000000u; } exp -= 23; if (exp >= 0) { frac <<= exp; } else { frac >>= -exp; } sign = sign >> 31; return (frac ^ sign) - sign;그렇게 작성한 위 코드는 틀린 코드이다.
ERROR: Test floatFloat2Int(0[0x0]) failed... ...Gives 2[0x2]. Should be 0[0x0]0 일 때 2를 return한다고 한다.
코드에서는 float의 normalization 여부와 상관 없이 normalized라고 가정하고 가상의 1,
(1 << 23)을 붙여 주었다.
하지만 문제될 게 없다고 생각했다.
이유는 Denormalized된 값인 경우 exp 값이 충분히 작아 1을 붙였는지 여부와 상관 없이 0이 될 거라 생각해서이다.문제의 0을 예로 들어보자면, exp 값이 0 - 127 - 23 = -150 ,
(1 <<23) >> 150 == 0이 되리라 생각했다.틀린 이유는 31 이상 shift 연산은 C에서 undefined기 때문이다.
결국 31 이상의 shift를 요구하는 매우 작은 값은 미리 0이 되도록 코드를 수정하였다.그렇게 완성한 최종본.
int floatFloat2Int(unsigned uf) { int sign = uf & (1 << 31); int exp = (uf ^ sign) >> 23; int frac = (uf & 0x00FFFFFF) | (1 << 23); /* bias */ exp -= 127; /* Value out of range (including NaN and infinity) */ if (exp > 31) { return 0x80000000u; } /* Seems unnecessary, but shifting more than 31 is undefined */ if (exp < 0) { return 0; } exp -= 23; if (exp >= 0) { frac <<= exp; } else { frac >>= -exp; } sign = sign >> 31; return (frac ^ sign) - sign; }
floatPower2
/* * floatPower2 - Return bit-level equivalent of the expression 2.0^x * (2.0 raised to the power x) for any 32-bit integer x. * * The unsigned value that is returned should have the identical bit * representation as the single-precision floating-point number 2.0^x. * If the result is too small to be represented as a denorm, return * 0. If too large, return +INF. * * Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while * Max ops: 30 * Rating: 4 */2의 x승을 float으로 반환해야 한다.
x가 127보다 크다면 범위를 벗어나니 INF를, x가 -126에서 127이면 Normalized 값으로 bias를 더해서 지수부에 넣어준다.
x가 -127 - 22 에서 -127 이면 Denormalized 값으로, $2^{-127}$
(1 << 22)를 다음과 같이 땡겨주면 된다.그 이하는 0을 반환한다.
FINAL CODE
unsigned floatPower2(int x) { x += 127; if (x >= 255) { /* +INF */ return 0xFF << 23; } else if (x > 0) { /* Normalized */ return x << 23; } else if (x > -23) { /* Denormalized */ return 1 << -x; } else { /* Too small */ return 0; } }끝
- 0 이 아닌 양수: