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

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

CSAPP/Lab Session
민호이 민호이 2025. 1. 9. 01:00
목차
  1. 1. 기초 비트 연산 (Basic Bit Operations)
  2. a. bitXor (1)
  3. b. bitAnd (1)
  4. c. bitNor (1)
  5. d. bitOr (1)
  6. 2. 기초 비트 다루기
  7. a. getByte (2)
  8. b. reverseBytes (3)
  9. c. logicalShift (3)
  10. 3. 기초 2의 보수
  11. a. Tmin (1)
  12. b. Tmax (1)
  13. c. negate (2)
  14. d. sm2tc (4)
  15. e. tc2sm (4)

아래의 내용들은 시스템 프로그래밍(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;
}
저작자표시 (새창열림)
  1. 1. 기초 비트 연산 (Basic Bit Operations)
  2. a. bitXor (1)
  3. b. bitAnd (1)
  4. c. bitNor (1)
  5. d. bitOr (1)
  6. 2. 기초 비트 다루기
  7. a. getByte (2)
  8. b. reverseBytes (3)
  9. c. logicalShift (3)
  10. 3. 기초 2의 보수
  11. a. Tmin (1)
  12. b. Tmax (1)
  13. c. negate (2)
  14. d. sm2tc (4)
  15. e. tc2sm (4)
'CSAPP/Lab Session' 카테고리의 다른 글
  • [CSAPP] Datalab :: bits.c - 완벽 풀이, 해설 (3)
  • [CSAPP] Datalab :: bits.c - 완벽 풀이, 해설 (2)
  • [CSAPP] Datalab :: Bit Counting Algorithms (bitCount, countOneBits)
민호이
민호이
민호이
ChungCODE
민호이
전체
오늘
어제
  • Categories (128)
    • 스포츠 (6)
    • 인공지능 (5)
    • 주식 (6)
      • 경제 주식 전망 (5)
      • ETF (9)
    • CSAPP (4)
      • Lab Session (4)
      • Concepts (0)
    • C (19)
    • Java (24)
    • Rust (44)
      • Concepts (27)
      • Libraries (17)
    • PS (2)
    • 국내 소식 (3)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • c++
  • 최대공약수
  • 최소공배수
  • 알고리즘
  • 코드업
  • 유클리드 호제법
  • C
  • 수학

최근 댓글

최근 글

반응형
hELLO · Designed By 정상우.v4.2.1
민호이
[CSAPP] Datalab :: bits.c - 완벽 풀이, 해설 (1)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.