[CSAPP] Datalab :: bits.c - 완벽 풀이, 해설 (1)

아래의 내용들은 시스템 프로그래밍(CS230; CSAPP)를 수강할 때 lab session을 진행하고 통과된 코드를 모아두었습니다. 특히 기본적으로 CMU에서 제공하는 datalab 자료 에서 구현하라고 한 함수들과 각 대학에서 주는 과제들을 통합했습니다. 모을 수 있는 함수들은 모두 모았으니 이 글 하나로도 datalab을 정복하실 수 있을 것입니다.

• [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part1
  bitXor, bitAnd, bitNor, bitOr / getByte, reverseBytes, logicalShift / Tmin, Tmax, negate, sm2tc, tc2sm
• [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part2
  bitMask, thirdBits, leastBitPos, replaceByte, copyLSB, rotateRight, rotateLeft / isTmin, isTmax / isPositive, isNonNegative, isNegative, isNonZero / isLessOrEqual, isNotEqual, isPower2
• [CSAPP/Lab Session] - [CSAPP] Datalab :: bits.c (시스템 프로그래밍, 데이터랩) - Part3
  logicalNeg, bang, conditional, isAscii / allOddBits, allEvenBits, anyOddBit, anyEvenBit, byteSwap, bitParity, bitCount, countOneBits, greatestBitPos, howManyBits, leftBitCount, countPattern / addOk, subOk, subOverflowFree, isLessOrEqual, absVal

1. 기초 비트 연산 (Basic Bit Operations)

a. bitXor (1)

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(~x&~y) & ~(x&y);
}

b. bitAnd (1)

/* 
 * 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);
}

c. bitNor (1)

/* 
 * bitNor - ~(x|y) using only ~ and & 
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
  return ~(~(~x & ~y));
}

d. bitOr (1)

/* 
 * bitOr - x|y using only ~ and & 
 *   Example: bitOr(6, 5) = 7
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */

int bitOr(int x, int y) {
   return ~( (~x) & (~y) );
}

2. 기초 비트 다루기

a. getByte (2)

/* 
 * 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) {
  return (x >> (n << 3)) & 0xFF;
}

b. reverseBytes (3)

/*
 * reverseBytes - reverse the bytes of x
 *   Example: reverseBytes(0x01020304) = 0x04030201
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int reverseBytes(int x) {
  int n = 0x00;
  n = n | ((x >> 24) & 0xFF);
  n = n | ((x >> 16) & 0xFF) << 8;
  n = n | ((x >> 8) & 0xFF) << 16;
  n = n | (x & 0xFF) << 24;
  return n;
}

c. logicalShift (3)

/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 1 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  return (x >> n) & ~(~0 << (32 + (~n + 1)));
}

3. 기초 2의 보수

a. Tmin (1)

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
 int tmin(void) {
    return (1 << 31);
}

b. Tmax (1)

/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
  int x = 1;
  return ~(1 << 31);
}

c. negate (2)

/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}

d. sm2tc (4)

/*
 * sm2tc - Convert from sign-magnitude to two's complement
 *   where the MSB is the sign bit
 *   Example: sm2tc(0x80000005) = -5.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int sm2tc(int x)
{
  int sign = x >> 31;
  int signDigit = sign << 31;
  return (((x ^ sign) | signDigit) + !!(sign));
}

e. tc2sm (4)

/* 
 * tc2sm - Convert from two's complement to sign-magnitude 
 *   where the MSB is the sign bit
 *   You can assume that x > TMin
 *   Example: tc2sm(-5) = 0x80000005.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 4
 */
int tc2sm(int x) {
  int sign = x >> 31; // sign mask
  int mag = (sign & (~x + 1)) | (~sign & x);
  return sign << 31 | mag;
}