[컴퓨터시스템프로그래밍] CS:APP Data lab bits.c Solution

시스템 프로그래밍 과제였던 CS:APP Lab assignments의 bits.c 해답이다. 너무나 어려웠던 과제... 일부는 구글링해 참고하였다. 

 

최대 8bit의 상수 사용, 사용 가능한 연산자 제한, 연산자 개수 제한 등으로 인해 원래도 어려운 문제들이었지만, 교수님이 The “Beat the Prof” Contest 를 진행하셔서 더 힘들었다. 재미를 위해서 추가점수..... 괜히 3학년 과목이 아닌가 싶기도 했다. 

 

byteSwap

/*
 * byteSwap - swaps the nth byte and the mth byte
 *  Examples: byteSwap(0x12345678, 1, 3) = 0x56341278
 *            byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD
 *  You may assume that 0 <= n <= 3, 0 <= m <= 3
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 25
 *  Rating: 2
 */
int byteSwap(int x, int n, int m) // ops: 11
{
    int n_shift = n << 3; // n*8 -> n byte
    int m_shift = m << 3; // m*8 -> m byte

    int n_byte = (x >> n_shift) & 0xff; // extract nth byte
    int m_byte = (x >> m_shift) & 0xff; // extract mth byte

    // (A ^ B) ^ B = A ^ (B ^ B) = A
    // (A ^ B) ^ A = (A ^ A) ^ B = B

    int mask = n_byte ^ m_byte;

    return x ^ ((mask << n_shift) | (mask << m_shift));
}

n번째 byte와 m번째 byte를 교환하는 문제 exclusive or 연산자의 활용이 돋보이는 문제였다.  

 

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) // ops: 24
{
    int h0f0f = 0x0f | (0x0f << 8);    // 0xffff. 0000 0000 0000 0000 1111 1111 1111 1111
    int step3 = h0f0f | (h0f0f << 16); // 0x0f0f0f0f. 0000 1111 0000 1111 0000 1111 0000 1111
    int step2 = step3 ^ (step3 << 2);  // 0x33333333. 0011 0011 0011 0011 0011 0011 0011 0011
    int step1 = step2 ^ (step2 << 1);  // 0x55555555. 0101 0101 0101 0101 0101 0101 0101 0101

    x = (x & step1) + ((x >> 1) & step1); // sum 2-bits
    x = (x & step2) + ((x >> 2) & step2); // sum 4-bits
    x = (x + (x >> 4)) & step3;           // sum 8-bits
    x = x + (x >> 8);                     // sum 16bits
    x = (x + (x >> 16)) & 0xff;           // sum all

    return x;
}

그냥 어려웠다. 이 역시 exclusive or 연산자를 활용해 mask를 만들고 인접한 2bit씩, 4bit씩, ...., 확장해가며 더해준다. 연산자 수를 줄여야 해서 더 어려웠다. 

 

bitReverse

/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7C3D591
 *
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x) // ops: 34
{
    // 1000 0000 0000 0000 0000 0000 0000 0010
    // 0100 0000 0000 0000 0000 0000 0000 0001

    // 76543210 >> 1 & 01010101 -> 07050301
    // 76543210 & 01010101 << 1 -> 60402000
    // + -> 67452301
    int step5 = 0xff | (0xff << 8);   // 0xffff. 0000 0000 0000 0000 1111 1111 1111 1111
    int step4 = step5 ^ (step5 << 8); // 0x00ff00ff. 0000 0000 1111 1111 0000 0000 1111 1111
    int step3 = step4 ^ (step4 << 4); // 0x0f0f0f0f. 0000 1111 0000 1111 0000 1111 0000 1111
    int step2 = step3 ^ (step3 << 2); // 0x33333333. 0011 0011 0011 0011 0011 0011 0011 0011
    int step1 = step2 ^ (step2 << 1); // 0x55555555. 0101 0101 0101 0101 0101 0101 0101 0101

    x = ((x >> 16) & step5) | (x << 16);         // reverse 16-bits
    x = ((x >> 8) & step4) | ((x & step4) << 8); // reverse 8-bits
    x = ((x >> 4) & step3) | ((x & step3) << 4); // reverse 4-bits
    x = ((x >> 2) & step2) | ((x & step2) << 2); // reverse 2-bits
    x = ((x >> 1) & step1) | ((x & step1) << 1); // reverse 1-bits

    return x;
}

bitCount와 비슷하게 mask를 생성한다. 절반씩 쪼개서, 16bit, 8bit, .... , 1bit씩 뒤집는다.

 

copyLSB

/*
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) // ops: 2
{
    // 0000 0001
    // 1000 0000
    // 11111111
    return (x << 31) >> 31;
}

쉬어가는 문제. arithmetic right shift를 이용한다. 

 

evenBits

/*
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int evenBits(void) // ops: 4
{
    int result = 0x55;                // 01010101
    result = result | (result << 8);  // 01010101 01010101
    result = result | (result << 16); // 0101 0101 0101 0101 0101 0101 0101 0101

    return result;
}

역시 쉬운 문제. 최대 8bit의 상수만 사용할 수 있기 때문에 bit shift 연산자와 | 연산자를 이용해 확장해준다.

 

isNegative

/*
 * isNegative - return 1 if x < 0, return 0 otherwise
 *   Example: isNegative(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNegative(int x) // ops: 2
{
    // return MSB
    return (x >> 31) & 1;
}

힐링 문제. two's complement system이므로 MSB를 return해준다. 

 

absVal

/*
 * absVal - absolute value of x
 *   Example: absVal(-1) = 1.
 *   You may assume -TMax <= x <= TMax
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int absVal(int x) // obs: 3
{
    int mask = x >> 31; // expand sign bit
    // when x is negative, mask is 0xffffffff : -1.
    // when x is positive, mask is 0x0. A ^ 0 = A

    return (x + mask) ^ mask; // x ^ 0xffffffff reverse x
}

조금 어려웠던 문제. 앞선 문제에서 exclusive or 연산자에 대해 조금 익숙해진 후, 연산자를 줄이기 위해 사용하였다. two's complement system에서 -1은 모든 bit가 1이므로, x가 음수이면 이를 양수로 변환하는 과정을 그대로 따라가게 된다. x가 양수면 0과의 exclusive or 연산이므로 그대로 x가 반환된다. 

 

sign

/*
 * sign - return 1 if positive, 0 if zero, and -1 if negative
 *  Examples: sign(130) = 1
 *            sign(-23) = -1
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 10
 *  Rating: 2
 */
int sign(int x) // ops: 4
{
    // when x is zero, !x is 1, !!x is 0
    // when x is nonzero, !x is 0, !!x is 1
    // x >> 31: copy sign bit
    return (x >> 31) | (!!x);
}

힐링문제. 

 

isPower2

/*
 * isPower2 - returns 1 if x is a power of 2, and 0 otherwise
 *   Examples: isPower2(5) = 0, isPower2(8) = 1, isPower2(0) = 0
 *   Note that no negative number is a power of 2.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int isPower2(int x) // ops: 10
{
    // 100 - 1 -> 011. 100 & 011 -> 000
    // 101 -1 -> 100
    // !!x : return 0 when x is 0, return 1 when x isn't 0
    // !(x & (x + ~0)) : return 1 when x is a power of 2
    // !(x >> 31) : return 1 when sign bit of x is 0
    // x isn't zero & x is power of 2 & x is positive
    // return !!x & !(x & (x + ~0)) & !(x >> 31);
    return !!x & !(x & (x + ~0)) & !(x >> 31);

}

x가 2의 거듭제곱인지 판단하는 코드. 2의 거듭제곱인 경우, binary number에서 1이 하나라는 점을 이용한다. 0이 아니고, 음수가 아니면서 2의 거듭제곱이면 1을 반환한다.

 

isTmin

/*
 * isTmin - returns 1 if x is the minimum, two's complement number,
 *     and 0 otherwise
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmin(int x) // ops: 4
{
    // -2^31
    // 1000 0000 0000 0000 0000 0000 0000 0000
    return !((x + x) | (!x)); // !(x + x) & (!!x)
}

two's complement number에서 minimum인 Tmin은 sign bit만 1이므로, Tmin + Tmin은 overflow로 0이 된다. 

 

isPallindrome

/*
 * isPallindrome - Return 1 if bit pattern in x is equal to its mirror image
 *   Example: isPallindrome(0x01234567) = 0, isPallindrome(0x0123C480) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int isPallindrome(int x) // ops: 32
{
    // 0x0123C480: 0000 0001 0010 0011 1100 0100 1000 0000
    int step1 = 0x55 | (0x55 << 8); // 0x5555. 0101 0101 0101 0101
    int step2 = 0x33 | (0x33 << 8); // 0x3333. 0011 0011 0011 0011
    int step3 = 0x0f | (0x0f << 8); // 0x0f0f. 0000 1111 0000 1111
    int step4 = 0xff;               // 0xff. 0000 0000 1111 1111

    int half1 = x >> 16;                  // 0000 0001 0010 0011
    int half2 = x & (step4 | step4 << 8); // 1100 0100 1000 0000

    half1 = ((half1 >> 1) & step1) | ((half1 & step1) << 1);
    half1 = ((half1 >> 2) & step2) | ((half1 & step2) << 2);
    half1 = ((half1 >> 4) & step3) | ((half1 & step3) << 4);
    half1 = ((half1 >> 8) & step4) | ((half1 & step4) << 8);
    // half1 : 1100 0100 1000 0000

    return !(half1 ^ half2);
}

상위 16bit와 하위 16bit로 쪼개서, 한쪽을 뒤집은 bit가 나머지와 같은지 판단한다. bitReverse와 유사하다.

 

signMag2TwosComp

/*
 * signMag2TwosComp - Convert from sign-magnitude to two's complement
 *   where the MSB is the sign bit
 *   Example: signMag2TwosComp(0x80000005) = -5.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int signMag2TwosComp(int x) // ops: 6
{
    // 0x80000005: 1000 0000 0000 0000 0000 0000 0000 0101 -> 1111 1111 1111 1111 1111 1111 1111 1011
    // ~(0x80000005) : 0111 1111 1111 1111 1111 1111 1111 1010

    // 0000 0101 -> 0000 0101
    // 1001 0110 -> 0110 1001 + 1000 0001 -> 1110 1010
    // let A = x, B = x >> 31
    // (A'+ 1000 0000 0000 0000 0000 0000 0000 0001)B + AB' -> A ^ B + 0x80000001 & B
    int copySign = x >> 31;

    return (x ^ copySign) + (((0x80 << 24) + 1) & copySign);
}

sign-magnitude system을 기준으로 입력된 정수를 반환, 즉 two's complement로 변환하는 문제이다. 

 

floatNegate

/*
 * floatNegate - 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 floatNegate(unsigned uf) // ops: 3
{
    // NaN
    if ((uf & 0x7FFFFFFF) > 0x7F800000) // exp is 0xff, frac isn't 0
        return uf;

    return uf ^ 0x80000000; // set sign bit to 1
}

NaN을 판정하는게 어려웠던 문제. exponent의 모든 bit가 1이고, fraction bit가 0이 아닐 경우 NaN인데, 이를 위와 같이 표현할 수 있음에 놀랐다. 

 

floatInt2Float

/*
 * floatInt2Float - 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 floatInt2Float(int x) // ops: 25
{
    unsigned sign = x & 0x80000000; // sign bit
    unsigned exp;                   // exponent
    unsigned frac;                  // fraction
    int E = 1;                      // E
    unsigned roundBit;              // rounding

    if (!x) // x is 0
        return 0;
    else if (x == 0x80000000) // x is -0
        return 0xcf000000;

    if (sign)   // x is negative
        x = -x; // absolute value

    while ((x >> E))
        E++;

    E--;           // adjust E as exact exponent value
    exp = E + 127; // add bias

    x = x << (31 - E);          // normalize
    frac = (x >> 8) & 0x7fffff; // extract fraction bits

    if (E > 23) // rounding
    {
        roundBit = x & 0xff;
        if ((roundBit > 128) || ((roundBit == 128) && (frac & 0x1)))
        {
            frac++;
            if (frac >> 23)
            {
                exp++;
                frac = 0;
            }
        }
    }

    return sign | (exp << 23) | frac;
}

그냥 너무 어려웠던 문제, 아래의 floatScale64와 함께 overflow와 rounding 처리가 어렵다. 

 

floatScale64

/*
 * floatScale64 - Return bit-level equivalent of expression 64*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: 35
 *   Rating: 4
 */
unsigned floatScale64(unsigned uf) // ops: 11
{
    int sign = uf & 0x80000000; // extract sign bit
    int float64 = 6; // for multiply 64, shift 6
    int exp; // exponent

    while (float64--)
    {
        exp = uf & 0x7f800000; // extract exponent
        if (!exp) // denormalized
            uf = sign | (uf << 1); // multiply 2

        else if (exp != 0x7f800000) // normalized, uf isn't inf or NaN
        {
            uf = uf + 0x800000; // multiply 2
            exp = uf & 0x7f800000; // extract exponent

            if (exp == 0x7f800000) // inf
                uf = uf & 0xff800000; // set frac to 0s
        }
    }

    return uf;
}

Datalab의 이전 문제들 중에 2를 곱하는 문제가 있었는데, 64를 곱하도록 변형된 문제다. 2를 곱할 경우는 overflow가능성이 없지만 64를 곱할 경우 exponent의 overflow 가능성이 현저히 커지면서 처리가 필요했다. 

 

floatAbsVal

/* 
 * floatAbsVal - Return bit-level equivalent of absolute value of 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 floatAbsVal(unsigned uf) { // ops: 2
    // 0000 0101 -> 0000 0101
    // 1001 0110 -> 0110 1001 + 1 -> 0110 1010
    // let A = uf,
    // A'B + AB'
    unsigned abs = uf & 0x7fffffff;

    // NaN
    if (abs > 0x7F800000)// exp is 0xff, frac isn't 0
        return uf;

    return abs;
}

나름 쉬웠던 문제. 연산자 수를 줄이기 위해 abs를 먼저 만들고 NaN을 판정한다.