[시스템 프로그래밍] - 2022년도 Datalab

 

 

부족한 부분이 많아 코드가 그리 깔끔하지는 않습니다.. ㅠ

(시프 다들 화이팅하세요😊)

 

 

 

 

🧐 addOK

/*
 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000,0x80000000) = 0,
 *            addOK(0x80000000,0x70000000) = 1,
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOK(int x, int y) {
    /*
     * Overflow가 발생하는 경우는 다음과 같다.
     *  (1) MSB_X = 0, MSB_Y = 0, MSB_(X+Y) = 1
     *  (2) MSB_X = 1, MSB_Y = 1, MSB_(X+Y) = 0
     *
     * 따라서
     *  MSB_X [XOR] MSB_Y 의 결과가 0이고,
     *  MSB_(X+Y) [XOR] MSB_X 의 결과가 1인 경우
     * Overflow 가 발생된 경우입니다.
     */
    int xMSB = x>>31;
    int yMSB = y>>31;
    int xyMSB = (x+y)>>31;

    return !((~(xMSB ^ yMSB) & (xyMSB ^ xMSB)));
}

 

처음에는 캐리비트를 통한 오버플로우 검출을 하려 시도했습니다.

그러나 캐리비트의 검출이 생각보다 어려웠기에 포기한 후, 다음과 같은 방법으로 구했습니다.

 

우선 덧셈에서 Overflow가 발생하는 경우는 다음 두 경우입니다.

 

	x의 MSB(또는 부호비트)	y의 MSB	x+y의 MSB
case 1	1	1	0
case 2	0	0	1

 

위 두가지 경우에만 0을 반환하도록 논리식을 작성하였습니다.

 

 

 

$x$ 와 $y$,  $x+y$ 의 부호비트를 각각 $x_s, \;y_s, \;(x+y)_{s}$ 라 하겠습니다.

처음으로는 $x$ 와 $y$ 의 부호비트를 통해 오버플로우 가능성이 있는 경우 1을 반환하도록 식을 작성했습니다.

$(x_{s} $  ⊕  $y_{s})$ 는 위 두가지 경우 0을 반환합니다. (⊕는 XOR 연산을 의미합니다.) 
그렇지 않은 경우 0이 아닌 값을 반환합니다. (코드상으로는 0xFFFFFFFF 을 반환합니다.)

해당 값에 ~연산(NOT)을 사용하여,
0인 경우(false) -> 0이 아닌 값(false),
0이 아닌 경우(true) -> 0(true)으로 바꾸어줍니다.

즉 Overflow가 발생할 수 있는 조건이라면 0이 아닌 값을, 그렇지 않다면 0을 반환합니다.

두번째로는 $x+y$ 의 부호비트와, $x$ 의 부호비트를 통해 오버플로우 가능성을 체크했습니다.

만약 두 부호비트가 다른 경우 오버플로우가 발생할 수 있으며,
해당 경우 1을 반환하도록 아래 식을 작성하였습니다.
$(x+y)_s$  ⊕  $x_s$

Overflow가 발생할 수 있는 조건이라면 0이 아닌 값을, 그렇지 않다면 0을 반환합니다.

Overflow가 발생한 상황이라면 위 두 논리식의 AND 연산의 결과가 0이 아니어야 합니다.

그러나 Overflow가 발생하면 논리식의 결과는 0이어야 하므로,

AND 연산의 결과에 ! 연산을 취해줌으로써, 원하는 결과를 얻을 수 있습니다.

 

 

(추가적으로 $x >> 31$ 은  $x$가 양수인 경우 0x00000000,   x가 음수인 경우 0xFFFFFFFF 를 반환합니다.

이는 x가 unsigned 타입이 아닌 signed int 이므로, 부호비트가 1인 경우 >> 연산을 수행하면 MSB가 1로 채워지기 때문입니다.)

 

 

 

 

 

 

 

 

 

🧐 allOddBits

/*
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
    /*
     * 0xAA = 10101010
     * 만약 x의 모든 홀수 비트가 1인 경우
     * x & 0xAAAAAAAA 의 결과(1)는 0xAAAAAAAA 입니다.
     *
     * 만약 A == B 라면,  A ^ B 의 결과는 0 이므로,
     *
     * 위 결과(1) 과 0xAAAAAAAA 의 ^ 연산의 결과는 0 또는 0이 아닌 수 이므로,
     * ! 연산을 통해 원하는 결과를 반환해줍니다.
     */
    int evenMask = 0xaa;
    evenMask = (evenMask << 8) | evenMask;
    evenMask = (evenMask << 16) | evenMask;
    return !((x & evenMask) ^ evenMask);
}

 

 

우선 홀수 자리 수가 무엇인지 알기 위해, 아래 이진수에서 홀수 자리 수를 주황색으로 표시하겠습니다.

$1_7$   $0_6$   $1_5$   $0_4$   $1_3$   $0_2$   $1_1$   $0_0$

 

풀이는 다음과 같습니다.

 

1010 1010 [1010]... 과 x를 AND 연산 시켜주면 홀수 번째 비트만 남게됩니다.

 

이제 해당 연산의 결과와 다시 1010 1010 [1010] .. 을 XOR 연산시켜준다면 다음 두 결과를 얻을 수 있습니다.

홀수 자리 수가 모두 1인 경우 결과는 0

그렇지 않은 경우 결과는 0이 아닌 어떤 수

이때 모두 홀수인 경우 1, 그렇지 않은 경우 0을 반환해야 하므로, ! 연산을 통해 원하는 결과를 반환하도록 구현하였습니다.

 

 

 

 

 

 

 

🧐 bitNor

/*
 * bitNor - ~(x|y) using only ~ and &
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
    /*
     * -를 사용할 수 없으므로 드모르간의 법칙을 사용합니다.
     * (A) OR (B) 는 ((A)' AND (B)')' 입니다.
     *
     * 따라서
     * (A) NOR (B) 는 (A)' AND (B)'
     */
    return ~x & ~y;
}

 

드모르간 법칙을 쓰면 쉽게 풀리는 문제입니다.

 

주석을 참고해주세용 :D

 

 

 

 

🧐 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) {
    /*
     * 부동소수점 표현에서 양수와 음수는 부호비트(MSB)만이 차이납니다.
     *
     * 따라서 uf의 음수값은 0x80000000 과 uf를 XOR 한 값입니다.
     *
     *
     * (+ infinity <-> - infinity) 따라서 무한대는 고려하지 않습니다.
     * (+ 0 <-> - 0) 따라서 0의 경우도 고려하지 않습니다.
     *
     * 만약 NaN 인 경우, uf를 그대로 리턴해야 합니다.
     *
     * NaN 은 아래와 같이 판단할 수 있습니다.
     *  uf의 비트를 부호비트, exp, frac 세 부분으로 나누면, 비트 길이는 다음과 같습니다. [1][8][23],
     *  (1) exp 즉 [8] 이 0xff 인 경우
     *  (2) frac 즉 [23] 이 0보다 큰 경우
     *  (1) 과 (2) 를 모두 만족해야만 uf가 NaN 입니다.
     *
     * exp 는 아래와 같은 방법으로 얻을 수 있습니다.
     *  uf & 0 1111 1111 0000 0000 ....
     *  즉 uf & (ff << 23)
     *
     * frac 은 아래와 같은 방법으로 얻을 수 있습니다.
     *  uf << 9 의 값은 [23]0000..0 입니다.
     *  따라서 (uf << 9) >> 9 의 값은 [23] 이며, 그것이 frac 입니다.
     *
     *  ! 그러나 NaN의 경우, frac은 0이 아닙니다. !
     *
     *  따라서 frac 이 0인 경우, [23]0000..00 역시 0입니다.
     *  즉 우리는 frac의 정확한 값을 구하기 위해 >> 9 연산을 해주지 않아도 됩니다. (연산자 수 줄이기)
     */

    //비정규화 체크하기위만 Mask : 0 [1111 1111] 0000 0000 ...
    unsigned deserializeMask = (0xff << 23);

    unsigned exp = (uf & deserializeMask);

    unsigned frac = (uf << 9);

    // 부호 반전을 위해 XOR을 해줄 Mask: 1000 0000 0000 ...
    unsigned mask = 0x80 << 24;

    // NaN 판단 : exp가 1111 1111 이며, frac이 0 이상인 경우
    if ((exp == deserializeMask) && frac) return uf;

    // 부호값 반전하여 리턴
    return uf ^ mask;
}

 

 

 

 

 

🧐 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) {
    /*
     *
     * 만약 exp 가 0x00 인 경우
     *  -> 2를 곱한 값을 반환해야 하는데, 이때 부호도 유지해야 함.
     *
     *  만약 exp 가 0xff 인 경우 + frac이 0이 아닌 경우
     *   -> NaN 이므로 그대로 반환
     *
     *  나머지의 경우 exp에 1을 더해주면 된다.
     */

    unsigned MSB = (uf >> 31)<<31;

    unsigned deserializeMask = (0xff << 23);

    unsigned exp = (uf & deserializeMask);

    // 00인 경우 비정규화 -> 왼쪽으로 1칸 Shift(X2) + 부호비트
    if (exp == 0x00) return (uf << 1) + (MSB);

    // NaN이거나 무한대인 경우 (exp 가 1111 1111 인 경우)-> 값 그대로 반환
    if (exp == deserializeMask) return uf;

    // 정규화인 경우 exp + 1
    return uf + (0x01 << 23);
}

 

 

 

 

 

 

🧐 rempwr2

/*
 * rempwr2 - Compute x%(2^n), for 0 <= n <= 30
 *   Negative arguments should yield negative remainders
 *   Examples: rempwr2(15,2) = 3, rempwr2(-35,3) = -3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int rempwr2(int x, int n) {

    int remainderMask = (1 << n) + ~0;  // 000[1]000 + 1111111 =  000[0]111
    int remainder = x & remainderMask; // 나머지

    /*
     * remainderIsZeroThen0Else1 : remind가 0이면 0, 아니면 1
     * remainder는 1이 아닐 수도 있으므로 [!!]을 통해 0 또는 1의 값만 갖도록 하였음
     */
    int remainderIsZeroThen0Else1 = !!remainder;

    /*
     * remainderIsZeroThen0Else1 가 1일 경우 ->  2^n승
     * (= 나머지가 0이 아닌 경우)
     *
     * remainderIsZeroThen0Else1 가 0일 경우 ->  0
     * (= 나머지가 0인 경우)
     */
    int twoPowerN = remainderIsZeroThen0Else1 << n;

    /*
     * -A = ~A(2의 보수) + 1
     * -2^n = ~2^n + 1
     *
     * 0인 경우 그대로 0이다.
     */
    int negative2PowerN = ~twoPowerN + 1;

    /*
     * 나머지 값이 음수인 경우 처리해주기 위해 사용한다
     *
     * x가 음수인 경우 : 0xFFFFFFFF
     * x가 양수인 경우 : 0x00000000
     */
    int MSBMask = x >> 31; // 11...11 or 00..00

    /**
     * 1. [x]가 양수인 경우.
     *    -> MSBMask가 0이므로, &연산의 결과는 항상 0, 따라서 더해도 결과에 지장이 없다.
     *
     * 2. [x]가 음수인 경우.
     *  2-1. 나머지[remainder]가 0인 경우
     *      -> remainderIsZeroThen0Else1 가 0이므로, negative2PowerN도 0이다.
     *         따라서 0 & ??? 의 형식이므로, 결국 0이며, 더해져도 결과에 지장이 없다.
     *
     *  2-2. 나머지가 0이 아닌 경우
     *       -> negative2PowerN 가 -2^n 이다.
     *          음수를 나눠준 경우, 양수로 나온 나머지에 -2^n을 해주어야 알맞은 음수 나머지가 나온다.
     *          예를 들어  -35 / 8의 경우, 
     *           35 = 0010 0011
     *          -35 = 1101 1101
     *			 8로 나누므로, remainderMask = 0000 0111
     *           즉 1101 1101 & 0000 0111 = 0000 0101 = +5이다
     *           +5 - 2^3 = -3 이므로, -2^n을 해주어야 정확한 나머지가 나온다.
     *          
     *           이는 다음과 같은 식으로도 표현 가능한데,
     *			 -35 = 8 * -5 + 5 이지만, 이를 아래와 같이 바꿔주어야 한다.
     *			 -35 = 8 * -4 - 3
     */
    return (remainder) + (negative2PowerN & MSBMask);
}