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

아래의 내용들은 시스템 프로그래밍(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

float값 다루기: floatAbsVal, floatisEqual, floatIsLess, float_neg, float_abs
float 특수 연산: mulFiveEights, divpwr2
float 어려운 연산: float_i2f, float_f2i, float_twice,

1. bang없는 논리 연산

a. logicalNeg, bang (4)

logicalNeg나 bang으로 불리우는 함수입니다.

이 함수는 datalab의 논리 연산 전체를 관통하는 내용입니다. 이를 확실하게 이해하면 다른 논리 연산 문제는 껌으로 느껴질 것입니다.

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  return ( ( (~x) & (~(~x+1)) ) >> 31 ) & 1;
}

핵심 아이디어

• 0만이 가진 고유한 성질:
  • x == 0일 때:
    • ~x는 모든 비트가 1 (-1).
    • ~x + 1도 -1 그대로.
    • 따라서, x와 ~(x + 1)의 비트가 완전히 동일.
  • x≠0일 때:
    • x와 ~(x + 1)은 항상 적어도 하나의 비트가 다릅니다.

코드의 본질

1. (x & ~(x + 1)):
   • x == 0일 때만, 이 연산의 결과가 -1(모든 비트가 1)이 됩니다.
   • x≠0라면 적어도 하나의 비트가 0이므로 결과는 0.
2. >> 31:
   • 이 결과에서 최상위 비트(부호 비트)를 추출합니다.
   • x==0일 때 -1의 부호 비트는 1이고, x≠0일 때는 0입니다.
3. & 1:
   • 최종적으로 부호 비트만 남겨 논리 값으로 변환합니다. x==0이면 1, x≠0이면 0.

요약

• 이 코드는 0만이 가진 "자기 보수 + 자기 음수의 보수"가 같은 유일한 비트 패턴이라는 성질을 이용해 x=0인지 확인합니다. 이를 통해 부정 연산을 비트 수준에서 구현한 것입니다.

b. conditional (3)

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
    x = !!x;
    x = ~x+1; 
    return (x & y) | (~x & z); 
}

05

c. isAscii (3)

/*
 * isAscii - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAscii(0x35) = 1.
 *            isAscii(0x3a) = 0.
 *            isAscii(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAscii(int x)
{
  int l1 = x + (~0x30 + 1); // x - 0x30
  int l2 = 0x39 + (~x + 1); // 0x39 - x
  return !((l1 | l2) >> 31);
}

2. 비트 패턴 인식 및 비교

a. allOddBits, allEvenBits (2)

/*
 * 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) {
  int mask = 0xAA | (0xAA<<8) | (0xAA<<16) | (0xAA<<24);
  return !((x & mask) ^ mask);
}

03

• A 생성: 0xAAAAAAAA를 생성합니다. 이는 모든 홀수 비트가 1이고, 짝수 비트가 0인 비트 패턴입니다.
• x & A: x와 A의 홀수 비트를 비교합니다. x의 홀수 비트가 모두 1이라면 결과는 A와 동일합니다.
• (x & A) ^ A: x & A와 A를 비교합니다. 결과가 0이면 x의 홀수 비트는 모두 1입니다.
• !: 최종적으로 결과를 논리 부정하여:
  • x의 모든 홀수 비트가 1이면 1 반환.
  • 그렇지 않으면 0 반환.

/* 
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x) {  
  int mask = 0x55 | (0x55 << 8) | (0x55 << 16) | (0x55 << 24);
  return !((mask & x) ^ mask);
}

allOddBits와 같은 논리로 해결하면 됩니다.

b. anyOddBit, anyEvenBit (2)

/* 
 * anyOddBit - return 1 if any odd-numbered bit in word set to 1
 *   Examples anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int anyOddBit(int x) {
    int mask = 0xAA | (0xAA<<8) | (0xAA<<16) | (0xAA<<24);
    return !!(x & mask);
}

anyEvenBit도 allEvenBit와 같은 마스크를 적용하면 됩니다.

c. byteSwap (2)

/*
 * 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) {
  int n_off = n << 3;
  int m_off = m << 3;
  int block1 = x >> n_off & 0xFF;
  int block2 = x >> m_off & 0xFF;
  x = x & ~(0xFF << n_off) & ~(0xFF << m_off);
  x = x | (block1 << m_off) | (block2 << n_off);
  return x;
}

d. bitParity (4)

/*
 * bitParity - returns 1 if x contains an odd number of 0's
 *   Examples: bitParity(5) = 0, bitParity(7) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 4
 */
int bitParity(int x) {
  x = (x >> 16) ^ x;
  x = (x >> 8) ^ x;
  x = (x >> 4) ^ x;
  x = (x >> 2) ^ x;
  x = (x >> 1) ^ x;
  return x & 0x1;
}

핵심 동작

1. 누적 XOR:
   • x의 상위 비트와 하위 비트를 XOR 연산으로 결합하며, 비트를 점점 축소합니다.
   • 최종적으로 x는 하나의 비트로 축소됩니다. 이 비트는 0의 개수가 홀수인 경우 1, 짝수인 경우 0입니다.
2. x & 0x1:
   • 최종 결과의 마지막 비트만 남겨서 반환합니다.

본질 요약

• XOR 연산은 동일한 비트를 제거(짝수 개일 때 0)하고, 홀수 개일 때 1을 유지합니다.
• 따라서 모든 비트를 누적 XOR하면, 0이 홀수 개면 1, 짝수 개면 0을 반환합니다.

e. bitCount, countOneBits (4)

/*
 * bitCount - returns count of number of 1's in word
 * countOneBits - returns count of number of 1's in word
 *   Examples: countOneBits(5) = 2, countOneBits(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
int bitCount(int x)
{
  int cnt;
  int cntmask, m1, m2, m3, m4;
  cntmask = 0x11 | 0x11 << 8;
  cntmask = cntmask | cntmask << 16;
  cnt = (x & cntmask) + (x >> 1 & cntmask )+ (x >> 2 & cntmask) + (x >> 3 & cntmask);

  m1 = 0x0f | 0x0f << 8;
  m1 = m1 | m1 << 16;
  cnt = (cnt >> 4 & m1) + (cnt & m1);

  m2 = 0x00ff | 0x00ff << 16;
  cnt = (cnt >> 8 & m2) + (cnt & m2);

  m3 = 0xff | 0xff << 8;
  cnt = (cnt >> 16 & m3) + (cnt & m3);

  return cnt;
}

인터넷에 정말 많은 풀이가 돌아다니지만 가장 깔끔한 풀이법입니다.

종이 접기를 하면서 맞은편에 있는 비트들과 덧셈을 한다고 생각하면 이해하기 쉽습니다. 마스크를 생성하는 것이 부자연스러워 보이지, 논리는 간결합니다.

Cross counting을 적용하면 문제가 생겨서 neighbor counting를 적용해야 합니다.

둘을 혼용하면 논리가 복잡해져 mask를 활용한 neighbor counting만 적용했습니다.

자세한 풀이법은 아래 글을 참고해주세요.

[CSAPP/Lab Session] - [CSAPP] Datalab :: Bit Counting Algorithms (bitCount)

f. greatestBitPos (4)

/* 
 * greatestBitPos - return a mask that marks the position of the
 *               most significant 1 bit. If x == 0, return 0
 *   Example: greatestBitPos(96) = 0x40
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 70
 *   Rating: 4 
 */
int greatestBitPos(int x) {
    x = x | x >> 1;
    x = x | x >> 2;
    x = x | x >> 4;
    x = x | x >> 8;
    x = x | x >> 16;
    return x & ((~x >> 1) ^ (-1));
}

g. howManyBits (4)

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
   int sign, cnt, shift;
   x = x ^ (x >> 31);

   shift = !!(x >> 16) << 4; // 상위 16비트 검사
   x >>= shift;
   cnt += shift;

   shift = !!(x >> 8) << 3; // 상위 8비트 검사
   x >>= shift;
   cnt += shift;

   shift = !!(x >> 4) << 2; // 상위 4비트 검사
   x >>= shift;
   cnt += shift;

   shift = !!(x >> 2) << 1; // 상위 2비트 검사
   x >>= shift;
   cnt += shift;

   shift = !!(x >> 1); // 상위 1비트 검사
   x >>= shift;
   cnt += shift;

   cnt += x; // 최하위 비트 포함

   return cnt + 1; // 부호 비트를 포함하여 반환
}

07

조금 더 압축하여 쓸 수 있지만 직관적인 이해를 위해서 풀어서 썼습니다.

양수인 경우 최초로 1이 등장하는 비트를, 음수인 경우 최초로 0이 등장하는 비트를 계산하면 되기에 xor 연산을 사용하여 최초로 1이 등장하는 비트 번호를 구합니다.

가령 20번째 비트에 있다면 23 = 16 + 4 + 2 + 1의 과정으로 구해주는 것입니다. 각각의 코드 조각들은 이분탐색으로 그 여부를 검사하고 누적합니다.

h. leftBitCount (4)

/*
 * leftBitCount - returns count of number of consective 1's in
 *     left-hand (most significant) end of word.
 *   Examples: leftBitCount(-1) = 32, leftBitCount(0xFFF0F0F0) = 12
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 50
 *   Rating: 4
 */
int leftBitCount(int x) {
    int result = 0;
    int shift;

    int allOnes = !(~x);

    shift = !(~(x >> 16)) << 4;
    result += shift;
    x <<= shift;

    shift = !(~(x >> 24)) << 3;
    result += shift;
    x <<= shift;

    shift = !(~(x >> 28)) << 2;
    result += shift;
    x <<= shift;

    shift = !(~(x >> 30)) << 1;
    result += shift;
    x <<= shift;

    result += (x >> 31) & 1;

    return result + allOnes;
}

i. countPattern (6)

/*
 * countPattern - returns the number of found "1111" in the given number x
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 80
 *   Rating: 6
 */
int countPattern(int x)
{
  int m = 1 | (1 << 4), loc, res;
  m = m | (m << 8);
  m = m | (m << 16);

  loc = (x & (x >> 1) & (x >> 2) & (x >> 3) & m);
  loc += ((x >> 1) & (x >> 2) & (x >> 3) & (x >> 4) & m) << 1;
  loc += ((x >> 2) & (x >> 3) & (x >> 4) & (x >> 5) & m) << 2;
  loc += ((x >> 3) & (x >> 4) & (x >> 5) & (x >> 6) & m) << 3;


  res = loc & m;
  res += (loc >> 1) & m;
  res += (loc >> 2) & m;
  res += (loc >> 3) & m;

  res += res >> 16;
  res += res >> 8;
  res += res >> 4;
  return res & 0xF;
}

카이스트 데이터랩에 등장하는 문제입니다.

"1111" 패턴을 찾는 문제이고 마스크와 이분탐색을 통해서 간단히 구할 수 있습니다.

bitCount, countOneBits을 이해하면 쉽게 해결할 수 있습니다.

3. overflow 판단

a. addOk (3)

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

b. subOk, subOverflowFree (3)

/*
 * subOK - Determine if can compute x-y without overflow
 *   same function named "subOverflowFree"
 *   Example: subOK(0x80000000,0x80000000) = 1,
 *            subOK(0x80000000,0x70000000) = 0,
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOk(int x, int y)
{
  int sign_x = (x >> 31);
  int sign_y = (y >> 31);
  int sign_diff = ((x + (~y + 1)) >> 31); // x-y sign

  int neg_overflow = sign_x & (!sign_y) & (!sign_diff);
  int pos_overflow = (!sign_x) & sign_y & sign_diff;
  return !(neg_overflow | pos_overflow);
}

c. 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 sign_x = x >> 31 & 1;
  int sign_y = y >> 31 & 1;
  return ((sign_x & !sign_y) | !(sign_x ^ sign_y) & (((x + ~y) >> 31) & 1));
}

isLess도 이에 기반하여 쉽게 풀 수 있습니다.

overflow인 경우도 고려해야함을 잘 생각해봐요.

Part1 - isLessorEqual에도 똑같이 언급된 내용입니다.

d. absVal (4)

/* 
 * 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) {

  int sign = x >> 31;
  return (x + sign) ^ sign;
}

양수와 음수인 경우에 각각 어떻게 작동하는지 나눠서 생각하면 쉽습니다.

양수인 경우에는 그대로 파라미터가 전달됩니다.

음수인 경우에는 x에서 ~x+1를 구하는 과정을 legal operation을 피해서 작성하면 됩니다.

음수인 경우에 sign = -1입니다. 따라서 x-1를 연산한 뒤에 (x-1)^(-1)을 시행하면 ~x+1를 얻을 수 있습니다.