[시스템 프로그래밍] Data Lab

 

 

 

 

1. bitNor

 

 

int bitNor(int x, int y) {
   return (~x) & (~y);
   // use de morgan law to use able operands.
}

 

 

드모르간 법칙을 사용해 사용 가능한 연산자만으로 bitNor를 구현하자.

~(x | y) => (~x) & (~y)

 

 

 

2. float_neg

 

 

unsigned float_neg(unsigned uf) {
   int res = (0x80 << 24) ^ uf; // change sign bit to make uf negative
   int expcmp = (0xFF << 23); // to get exp 
   int exp = expcmp & uf; // uf's exp part
   int frac = (uf << 9); // uf's frac part

   if(exp == expcmp && frac){ // NaN check
      return uf; // if NaN return uf. (the problem says)
   }else{
      return res; // if not NaN return res.
   }   

}

 

 

 

실수 uf가 주어지고, uf의 음수값을 반환해야 한다.

부동 소수점 표현을 사용했을 때 실수는 (-1)^S * M * 2^E 로 표현된다.

즉, S M E 는 각각 부호 / 유효 숫자 / 지수 로 표현된다.

 

입력으로 들어오는 uf는 unsigned int 타입으로, 4byte 크기를 가진다.

따라서 이진수로 표현 시 32bit 크기이다.

S비트는 MSB에 할당돼있고, 8비트는 E비트, 23비트는 M비트에 할당돼있다.

 

이제 세 가지 경우를 나눠서 생각해보자.

 

Normalized Value

exp != 00.. && exp != 11.. 인 경우이다.

즉, 이 경우는 주어진 uf의 부호 비트만 바꾸면 된다.

 

2. Denormalized Value

여기서는 다시 두 가지 경우로 나뉜다.

 

2-1. exp == 00... && frac == 00...

이 경우 주어진 수는 0을 의미하는데, 0에 음수를 취해봤자 0이다. 부호 비트만 바꿔서 반환하자.

2-2. exp == 00... && frac != 00...

이 경우 주어진 수는 0.0에 근접한 소수이니 부호 비트만 바꿔서 반환하자.

 

3. Special Value

다시 두 가지 경우로 나뉜다.

 

3-1. exp == 11.. && frac == 00..

무한대를 표시하니 고려하지 않아도 된다. 부호 비트만 바꿔서 반환하자.

3-2. exp == 11.. && frac != 00..

이 경우 주어진 수는 NaN이다.

문제에서 NaN은 uf를 그대로 반환하라고 했으니, uf를 반환하자.

 

즉, NaN인 경우만 찾아서 uf를 그대로 반환해주고, 나머지 경우는 uf에서 부호 비트만 바꿔서 반환해주면 된다.

 

(0x80 << 24) ^ uf : uf에서 부호 비트만 바꾼 결과

(0xFF << 23) & uf : uf에서 exp부분

(uf << 9) : uf에서 frac부분

 

 

 

 

3. allOddBits

 

 

 

int allOddBits(int x) {
   // 0xAAAAAAAA 
   // compare with 1010 1010 1010 1010 1010 1010 1010 1010 to check odd position.
   int compare = (0xAA << 8); // 0xAA00
   compare = compare | (0xAA); // 0xAAAA
   compare = (compare << 16) | compare; // 0xAAAA0000 | 0x0000AAAA = 0xAAAAAAAA
            
   return !((x & compare) ^ compare); 
   // x & compare : remain odd index of x
   // (x & compare) ^ compare : if odd index of x is 1, change to 0 and 0 to 1 vice versa
   // if all odd index of x was 1 result is 0 else result is 1
   // execute ! to get correct answer.
}

 

 

입력으로 들어온 값의 홀수 자리 수가 모두 1이면 1을 반환해야 한다.

주어진 수의 홀수 자리 수가 어떤 수인지 확인하기 위해 0xAAAAAAAA 비트를 사용하자. (1010 1010 1010 ...)

 

입력으로 들어온 x와 0xAAAAAAAA 비트를 & 연산 시 x의 홀수 자리 비트만 남게 된다.

이후 0xAAAAAAAA 비트와 위의 연산 결과를 ^ 연산 시 x의 홀수 자리 수가 1인 경우 0으로, 0인 경우 1로 바뀌게 된다.

 

즉, x의 홀수 자리 수가 모두 1이였으면 연산 결과가 0이 되고, 하나라도 1이 아니였다면 연산 결과가 0이 아니게 된다.

 

최종 연산 결과에 ! 연산을 수행한 값을 반환해주자.

 

0xAA << 8 : 0xAA00

0xAA00 + 0xAA = 0xAAAA

0xAAAA <<16 + 0xAAAA = 0xAAAAAAAA

 

 

 

 

4. rempwr2

 

 

int rempwr2(int x, int n) {
   int divisor = (1 << n) + ~0;  // 2^n - 1 
   int check = x >> 31; // x > 0 ? 0 : -1 
   int res = x & divisor; // if x is positive value, this will be answer.

   return (res) + (((~((!!res) << n)) + 1) & check);  
   // when it comes to positive value, just return res. res is answer.
   // if x is positive check is just 0. so (((~((!!res) << n)) + 1) & check) goes to 0
   // when it comes to negative value, return res + (-2^n)    
   // if x is negative check is 111... 
   // if x is negative and res is not 0 (((~((!!res) << n)) + 1) & check) goes to -2^n
   // if x is negative and res is 0 (((~((!!res) << n)) + 1) & check) goes to 0
}

 

 

x % (2^n) 결과를 반환해야 한다.

 

주어진 x을 2^n으로 나눈 나머지는 x와 (2^n – 1)을 & 연산한 결과와 같다.

입력으로 들어오는 x가 항상 양수라는 보장이 있으면 이대로 반환해도 되지만, x는 음수일 수 있다. 이에 따른 처리를 해 주자.

 

x가 음수 일 때는 음수의 나머지를 구해 줘야 된다.

2의 보수를 사용해 x와 (2^n – 1)을 & 연산한 결과에 2^n을 빼 주자.

 

int divisor = (1 << n) + ~0 : 2^n – 1을 의미한다.

int check = x >> 31 : 부호 비트를 가져오자. 양수인 경우 0, 음수인 경우 11...

int res = x & ((1 << n) + ~0) : 양수인 경우 이 자체로 답이지만 음수인 경우 여기에 2^n을 빼 주자.

 

(res) + ((~((!!res) << n)) + 1) & check : x가 양수인 경우 check는 0이 된다. res를 그대로 반환한다.

x가 음수이고 res 값이 0이 아닌 경우 !!res는 1이 되고 res에 2^n을 뺀 값을 반환한다.

x가 음수이고 res 값이 0인 경우 ((~((!!res) << n)) + 1) 값이 0이 되고 res값을 그대로 반환한다.

 

 

 

5. addOK

 

 

 

int addOK(int x, int y) {
   int signX = (x >> 31); // sign of x. >> is arithmetic shift in C
   int signY = (y >> 31); // sign of y
   int signSum = (x + y) >> 31; // sign of x+y

   // if x's sign bit is 1, signX to be 111....
   // if x's sign bit is 0, signX to be 000....
   
   int sameXY = !(signX ^ signY); // signX == signY ? 1 : 0
   int differentXSum = (signX ^ signSum); // signSUm == signX ? 0 : 1

   return !(sameXY & differentXSum); // signX == signY && signX != signSum ? 0 : 1

}

 

 

 

x+y 연산 결과가 오버플로우를 발생시키면 0을, 아니면 1을 반환해야 한다.

 

오버플로우는 x와 y의 부호가 같고 x+y의 부호가 x또는 y의 부호와 다를 때 발생한다.

 

int signX = (x << 31) : x의 부호 비트를 가져온다.

int signY = (y << 31) : y의 부호 비트를 가져온다.

int signSum = (x + y) <<31 : x+y의 부호 비트를 가져온다.

 

int sameXY = !(signX ^ signY) : x와 y의 부호가 같으면 1, 다르면 0이 저장된다.

int differentXSum =(signX ^ signSum) : x+y와 x의 부호가 같으면 0, 다르면 1이 저장된다.

 

!(sameXY & differentXSum) : x와 y의 부호가 같고, x+y의 부호와는 다르면 0을 반환한다.

 

 

 

6. float_twice

 

 

unsigned float_twice(unsigned uf) {

   int expcmp = (0xFF << 23); // to get exp
   int exp = expcmp & uf; // uf's exp part
   int sign = (0x80 << 24) & uf; // uf's sign bit

   if(exp == expcmp){ // if special value return uf
      return uf;
   }else if(exp == 0){ // if denormalized value return (uf << 1) exclude sign bit
      return sign | (uf << 1);
   }else{
      return uf + (1 << 23); // if normalized value return exp + 1
   }

}

 

 

입력으로 들어오는 uf에 대해 2*uf를 반환해야 한다.

 

float_neg에서 했던 것처럼 각각의 경우를 나눠서 생각해보자.

 

1. Normalized Value

exp != 00.. && exp != 11.. 인 경우이다.

Normalized를 2배 할 때는 exp 값에 1을 더해주면 된다.

 

2. Denormalized Value

여기서는 다시 두 가지 경우로 나뉜다.

 

2-1. exp == 00... && frac == 00...

이 경우 주어진 수는 0을 의미하는데, 2를 곱해봤자 0이다. 부호 비트를 제외한 나머지 비트를 한 칸씩 왼쪽으로 시프트한 값을 반환하자.

2-2. exp == 00... && frac != 00...

이 경우 주어진 수는 0.0에 근접한 소수이니 부호 비트를 제외한 나머지 비트를 한 칸씩 왼쪽으로 시프트한 값을 반환하자.

 

3. Special Value

다시 두 가지 경우로 나뉜다.

 

3-1. exp == 11.. && frac == 00..

무한대를 표시하니 고려하지 않아도 된다. uf를 반환하자.

3-2. exp == 11.. && frac != 00..

이 경우 주어진 수는 NaN이다.

문제에서 NaN은 uf를 그대로 반환하라고 했으니, uf를 반환하자.

 

즉, Normalized Denormalized Special 각각 반환하는 값이 다르다.

 

int expcmp = (0xFF << 23) : 주어진 값에서 exp부분만 빼오기 위한 값

int exp = expcmp & uf : uf에서 exp 부분

int sign = (0x80 << 24) & uf : uf에서의 부호 비트