0. 들어가기에 앞서...
솔직히 너무 아이큐 테스트 같았던 실습이었다. 막 몇 시간씩 한 function에 매달리고 있는 학생들도 있었는데, 내가 느끼기엔 한 1시간 정도 고민하다가 도저히 떠오르지 않으면 구글링 하는게 더 나을 듯 하다.
1. bitAnd
/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
return ~(~x | ~y); //드모르간의 법칙 이용
}
(...)
2. getByte
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: getByte(0x12345678,1) = 0x56
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 6
* Rating: 2
*/
int getByte(int x, int n) { //추출하고자 하는 byte에 해당하는 2자리의 16진수가
least significant bit 부터 위치하도록 해주는 function.
int shift = n << 3; //n이 0~3이면 0, 8, 16, 24만큼 right shift 해주기 위함.
x = x >> shift;
return x & 0xFF; //least significant 2자리 16진수를 추출
}
0x11223344라는 32비트 수가 있다고 하자.
그러면 n이 0~3일 때 각각 0x44, 0x33, 0x22, 0x11이 값이 된다.
따라서 n에 8을 곱한 만큼 right shift 한 뒤 0xFF의 mask를 씌워 추출한다고 생각하면 된다.
3. logicalShift
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) { //새로 생성된 부분에 해당하는 bit만 0으로 모두 바꾸어줌
int mask = ((1 << 31) >> n) << 1; //1111000........과 같은 형태의 mask 생성
x = x >> n; //Arithmetic shift 실행
return ~mask & x; //~overlap과 x의 bitAnd 연산 실행
}
기본적으로 arithmetic shift가 적용되므로 sign bit가 1일 경우 right shift를 하면,
shifting된 bit들이 모두 1이 된다. 그 부분을 모두 0으로 바꾸어 주면 된다.
4. bitCount
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) { //16진수 한개 단위로 1인 bit의 개수를 세고, 이를 더해주는 방식.
int count = 0x11 | (0x11 << 8); //0x00001111 생성.
int sum = 0;
int mask = 0xF | (0xF << 8); //0x00000F0F 생성.
count = count | (count << 16); //0x11111111 생성.
sum = x & count; //각 16진수 1개의 첫번째 bit가 1이면 1을 더해주고, 아니면 그대로 유지.
sum = sum + ((x >> 1)&count); //각 16진수 1개의 두번째 bit가 1이면 1을 더해주고,
아니면 그대로 유지.
sum = sum + ((x >> 2)&count); //위와 동일
sum = sum + ((x >> 3)&count); //위와 동일
sum = sum + (sum >> 16); //0~15번째 bit에서 1인 bit의 수와, 16~31번째 bit에서 1인
bit의 수의 합이 0~3번째 16진수 숫자에 저장되도록 함.
sum = (sum&mask) + ((sum >> 4)&mask);
return (sum & 0xFF) + (sum >> 8);
}
제일 쉬운 방식은 31번 shift를 해주면서 least significant bit가 1인지 검증하고, 그 횟수를 세면 된다.
근데 이런 방식으로 하면 Max ops를 한참 넘게 된다..
1비트를 한 단위로 보지 않고, 4비트(16진수 한 개)를 한 단위로 보면 코드를 짧게 줄일 수 있다.
5. bang
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
int notzero = x | (~x + 1); //0이 아니면 자신과, 자신의 음수와의 bitOr 연산을 했을 때
sign bit 가 1이 됨. (0x80000000의 경우에도 해당함.)
return (notzero >> 31) + 1; //notzero >> 31을 한 결과는 0이 아닌 경우 0xFFFFFFFF,
0인 경우 0이 되므로 여기에 1을 더한 결과를 출력하면 됨.
}
주석의 내용이 전부이다.
6. tmin
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1 << 31; //가장 작은 수는 0x80000000.
}
쉬어가는 코너.
7. fitsBits
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) { //left shift를 실행한 뒤 다시 right shift를 실행해서
원래 수와 같아지는 지를 비교해보는 function.
int shift = 33+ (~n); //left shift를 32-n번 시키기 위함.
int value = (x <<shift) >> shift; //left shift 실행한 뒤, 다시 right shift로 복원.
return !(value ^ x); //복원된 숫자와 x가 일치하면 1, 아니면 0을 출력.
}
left shift 했다가 다시 right shift로 비트들을 원상복귀 시켰을 때, 원래의 수와 일치하는 지를 보면 된다.
방법은 간단한데 생각하는 게 어려웠던 문제.
8. bitAnd
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int negative = x >> 31; //음수일 경우 0xFFFFFFFF가, 아닐경우 0이 저장됨.
int value = x + (negative & ((1 << n) + negative)); //bias를 원래 x에 더해준 값을
value에 저장.
return value >> n;
}
관건은 x가 음수일 경우이다. round toward zero이므로, 그냥 x>>n을 결과로 낼 경우
x가 음수일 때는 정답과 함수의 결과값이 차이가 나게 된다.
따라서 rounding을 고려하여 x에 bias를 더해주는 작업이 필요하다.
9. negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1; //2's complement에서 x의 음수는 ~x + 1임.
}
tmin과 마찬가지로 쉬어가는 코너.
10. isPositive
/*
* isPositive - return 1 if x > 0, return 0 otherwise
* Example: isPositive(-1) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 3
*/
int isPositive(int x) {
int signconverse = !(x >> 31); //음수일 경우 0, 아닐 경우 1이 저장됨.
return !x^signconverse; //양수일 경우 (0^1)=1이, 0이나 음수일 경우
(1^1)=0, (0^0)=0이 출력됨.
}
0 이상인지를 알려면 그냥 sign bit로 판별하면 되는데, 양수만을 판별해야 되서 살짝 까다로운 문제이다.
11. isLessOrEqual
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int xsign = (x >> 31) & 1;
int ysign = (y >> 31) & 1;
int dif = xsign^ysign;
int valuesign = ((~x + 1) + y) >> 31;
return (dif & xsign) | (!(dif | valuesign));
// 첫번째 경우는 y는 양수이고, x는 음수인 경우에 대해 overflow를 방지하기 위함.
// 두번째 경우는 x와 y가 같은 sign bit를 가졌을 때
y-x의 sign bit를 따져서 양수인지 판별.
}
그냥 y에서 x를 뺀 다음에 sign bit로 판별하면 되는 거 아닌가~? 라고 생각했다면 오산이다.
만약 y가 양수이고, x가 음수라면? 당연히 정답은 1이 나와야 하지만, overflow에 의해 0이 나올 수 있다.
이 문제의 관건은 x와 y의 sign bit가 다를 때 overflow를 고려해 주는 것이다.
12. ilog2
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) { //leftmost 1의 위치를 찾는 function.
int count = 0x11 | (0x11 << 8);
int sum = 0;
int mask = 0xF | (0xF << 8);
//1st section. leftmost 1부터 least significant bit까지 전체를 1로 채움.
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
//2nd section. 1의 개수를 bitcount한 뒤 1을 빼준 값을 출력.
count = count | (count << 16);
sum = sum + (x&count);
sum = sum + ((x >> 1)&count);
sum = sum + ((x >> 2)&count);
sum = sum + ((x >> 3)&count);
sum = sum + (sum >> 16);
sum = (sum&mask) + ((sum >> 4)&mask);
return ((sum & 0xFF) + (sum >> 8)) + (~0);
}
bitCount와 동일한 문제로 볼 수 있다.
leftmost 1의 위치에서 1을 뺀 것이 답이라는 건 알지만, 이를 어떻게 구현하는 지가 고민이다.
정답은 leftmost 1부터 least significant bit까지를 다 1로 채운 뒤, bitCount를 시행하면 위치를 알 수 있다.(!)
코드를 보면 2 section으로 나뉘어 있는데, 그에 대한 설명은 주석과 같다.
13. float_neg
/*
* float_neg - Return bit-level equivalent of expression -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 representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
int result = 0x80000000 ^ uf; //sign bit만 바꿔줌.
int exp = 0x7F800000 & uf;
int frac = 0x007FFFFF & uf;
if((exp == 0x7F800000) && frac) //exp가 11111111이고, frac이 0이 아닌 경우 NaN
return uf;
return result; //NaN이 아닌 경우에는 result를 출력.
}
unsigned uf 자체를 floating point expression으로 생각한 뒤 sign bit만 바꿔주는 함수이다.
NaN일 경우만 고려해주면 되는데, NaN은 exp bit가 모두 1이고, frac bit가 0이 아닌 경우 이므로, if문으로 쉽게 예외 처리해주면 된다.
14. float_i2f
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
int sign, bit, exp, frac, fracmask, round;
sign = x & 0x80000000;
fracmask = 0x7FFFFF;
if(x == 0)
return 0;
else if(x == 0x80000000){
exp = 158;
return 0xCF000000;
}
else{
if(sign) //x가 음수라면 먼저 양수로 바꿔줌.
x = -x;
bit = 1;
while((x>>bit) != 0) //x의 leftmost bit를 찾기 위해 while문 삽입.
bit++;
bit--;
exp = bit + 127;
x = x << (31 - bit);
frac = fracmask & (x >> 8);
if(bit > 23){ //부동소수점에서 rounding 계산.
round = x & 0xFF;
if((round > 128) || ((round == 128) && (frac & 1))){
frac++;
if(frac >> 23){
exp++;
frac = 0;
}
}
}
}
return sign | (exp << 23) | frac;
}
(...)
15. float_twice
/*
* float_twice - 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
*/
unsigned float_twice(unsigned uf) {
int exp = 0x7F800000 & uf;
int sign = 0x80000000 & uf;
if(exp == 0x7F800000)
return uf;
else if(exp == 0) //Denormalized를 2배할 때는 sign bit를 제외한 나머지 bit들을
1칸씩 left shift하면 됨.
return sign | (uf << 1);
else //Normalized를 2배할 때는 exp에 1을 더해주면 됨.
return uf + 0x00800000;
}
floating point를 공부했다면 denormalized와 normalized의 차이에 대해 알 것이다.
uf는 denormalized, normalized, NaN의 3가지 값을 가질 수 있다.
이 때 uf가 denormalized라면 sign bit를 제외한 나머지 bit을 1칸 left shift 하는 것이 2배하는 효과를 낸다.
uf가 normalized라면 그냥 exp에 1을 더해주는 것이 2배하는 효과를 낸다.
