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

아래의 내용들은 시스템 프로그래밍(CS230; CSAPP)를 수강할 때 lab session을 진행하고 통과된 코드를 모아두었습니다. 특히 기본적으로 CMU에서 제공하는 datalab 자료 에서 구현하라고 한 함수들과 각 대학에서 주는 과제들을 통합했습니다. 아래에 datalab 문제의 해설 및 풀이가 있으니 공부에 활용하세요. 데이터랩 과제와 지필고사를 준비할 때 유용하게 활용할 수 있을 것입니다.

 

다른 bits.c 시프 데이터랩 풀이를 보려면 아래에서 원하는 함수를 검색하세요!

• [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. 비트 패턴 생성하기

a. bitMask (3)

/*
 * bitMask - Generate a mask consisting of all 1's
 *   lowbit and highbit
 *   Examples: bitMask(5,3) = 0x38
 *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
 *   If lowbit > highbit, then mask should be all 0's
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int bitMask(int highbit, int lowbit) {
  return ~((~0 << highbit) << 1) & (~0 << lowbit);
}

b. thirdBits (1)

/*
 * thirdBits - return word with every third bit (starting from the LSB) set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 1
 */
int thirdBits(void) {
    int n = 1; //now move 1 over 3 bits
    n = (n << 3) + n; //looks like 1001
    n = (n << 6) + n; //1001001001
    n = (n << 12) + n; //1001001001001001001001
    n = (n << 24) + n; //10010010010010| stops here because over 32 bits 01001001001001001001001001001001
  return n;
}

04

c. leastBitPos (2)

/*
 * leastBitPos - return a mask that marks the position of the
 *               least significant 1 bit. If x == 0, return 0
 *   Example: leastBitPos(96) = 0x20
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int leastBitPos(int x) {
  return x & (~x + 1);
}

04

d. replaceByte (3)

/* 
 * replaceByte(x,n,c) - Replace byte n in x with c
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: replaceByte(0x12345678,1,0xab) = 0x1234ab78
 *   You can assume 0 <= n <= 3 and 0 <= c <= 255
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 3
 */
int replaceByte(int x, int n, int c) {
  int shift = n << 3;
  int mask = 0xFF << shift;
  return x & ~mask | c << shift;
}

05

e. copyLSB (2)

/* 
 * 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) {
  return (x << 31) >> 31;
}

06

f. rotateRight (2), rotateLeft (3)

/*
 * rotateRight - Rotate x to the right by n
 *   Can assume that 0 <= n <= 31
 *   Examples: rotateRight(0x87654321,4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3 
 */
int rotateRight(int x, int n) {
   int left = x << (32 + (~n + 1));
   int mask = ~((1 << 31) >> (n + ~0));
   int right = (x >> n & mask);
   return left | right;
}

07

/*
 * rotateLeft - Rotate x to the left by n
 *   Can assume that 0 <= n <= 31
 *   Examples: rotateLeft(0x87654321,4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int rotateLeft(int x, int n) {
  int left = x << n;
  int mask = ~(~0 << n);
  int right = (x >> (32 + (~n + 1))) & mask;
  return left | right;
}

04

2. 논리 비교 연산 - 범위

a. isTmin (1)

/*
 * 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) {
   int tmin = 1 << 31;
   return !(x ^ tmin);
}

07

b. isTmax (1)

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

07

3. 논리 비교 연산 - 부호

a. isPositive (3)

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

02

b. isNonNegative (3)

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

07

c. isNegative (2)

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

03

c. isNonZero (4)

/*
 * isNonZero - Check whether x is nonzero using
 *              the legal operators except !
 *   Examples: isNonZero(3) = 1, isNonZero(0) = 0
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int isNonZero(int x) {
  return  ((x | (~x + 1)) >> 31) & 0x01 ;
}

08

4. 논리 연산 비교 - 어려운 것

a. isLessOrEqual (3)

/* 
 * 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 signx = x >> 31 & 1;
  int signy = y >> 31 & 1;
  return ((signx & !signy) | !(signx ^ signy) & (((x + ~y) >> 31) & 1));
}

02

• 부호 확인:
  • signx와 signy는 각각 x와 y의 부호를 나타냅니다. (x >> 31 & 1은 가장 왼쪽 비트(부호 비트)를 추출합니다.)
  • 이를 통해 x와 y가 양수인지 음수인지 판별합니다.
• 부호가 다른 경우:
  • signx & !signy는 x가 음수이고 y가 양수일 때 1을 반환합니다. 이 경우 x≤yx \leq yx≤y는 항상 참이므로 바로 1을 반환합니다.
• 부호가 같은 경우:
  • !(signx ^ signy)는 x와 y의 부호가 같은지를 확인합니다. 만약 부호가 같다면, x + ~y를 계산해 두 값의 차를 구합니다.
  • 그 후 (x + ~y) >> 31 & 1은 이 차이가 음수인지 확인합니다. 음수이면 x<yx < yx<y이므로 1을 반환합니다.
• 최종 결과:
  • 부호가 다른 경우 또는 부호가 같고 x≤yx \leq yx≤y인 경우 1을 반환합니다

b. isNotEqual (2)

/* 
 * isNotEqual - return 0 if x == y, and 1 otherwise 
 *   Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNotEqual(int x, int y) {
  return !(!(x ^ y));
}

02

이 코드는 두 숫자 x와 y가 같으면 0, 다르면 1을 반환하는 함수입니다. 여기서는 XOR 연산을 이용해 숫자의 동일 여부를 확인합니다.

• x ^ y: XOR 연산은 두 숫자가 같으면 0, 다르면 1 이상의 값을 반환합니다.
• !(x ^ y): XOR 결과를 !로 반전시켜, 두 숫자가 같으면 1, 다르면 0이 되도록 합니다.
• !(!(x ^ y)): 다시 !를 적용하여, 두 숫자가 같으면 0, 다르면 1이 되도록 합니다.

c. isPower2 (4)

/*
 * 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: 60
 *   Rating: 4
 */
int isPower2(int x) {
    int sign = x >> 31;
    x = sign & (~x + 1) | ~sign & x;
    return !(x & (x-1)) & (!sign & !!x);
}

• 음수와 0 처리:
  • sign으로 x가 음수인지 확인합니다. 음수와 0은 2의 거듭제곱이 아니므로 제외합니다.
• x & (x - 1) :
  • 2의 거듭제곱인 숫자는 하나의 1 비트를 가지므로, x & (x - 1)은 항상 0입니다.
  • 예: x=8(10002)x = 8 (1000_2)x=8(10002​), x−1=7(01112)x - 1 = 7 (0111_2)x−1=7(01112​), x & (x - 1) = 0.
• 최종 결과:
  • x>0이고 x & (x - 1) = 0일 때만 1을 반환.