[스크랩] CS:APP 비트연산 과제 bits.c 답안

/*
 * CS:APP Data Lab
 *
 * bits.c - Source file with your solutions to the Lab.
 *          This is the file you will hand in to your instructor.
 *
 * WARNING: Do not include the <stdio.h> header; it confuses the dlc
 * compiler. You can still use printf for debugging without including
 * <stdio.h>, although you might get a compiler warning. In general,
 * it's not good practice to ignore compiler warnings, but in this
 * case it's OK.
 */
 
#include "btest.h"
#include <limits.h>
 
/*
 * Instructions to Students:
 *
 * STEP 1: Fill in the following struct with your identifying info.
 */
team_struct team =
{
   /* Team name: Replace with either:
      Your login ID if working as a one person team
      or, ID1+ID2 where ID1 is the login ID of the first team member
      and ID2 is the login ID of the second team member */
    "000000000000",
   /* Student name 1: Replace with the full name of first team member */
   "TREASURE4ME.BLOG.ME",
   /* Login ID 1: Replace with the login ID of first team member */
   "BLOG.NAVER.COM/TREASURE4ME",
 
   /* ANSWERS WRITTEN BY TREASURE4ME */
  
   /* The following should only be changed if there are two team members */
   /* Student name 2: Full name of the second team member */
   "",
   /* Login ID 2: Login ID of the second team member */
   ""
};
 
#if 0
/*
 * STEP 2: Read the following instructions carefully.
 */
 
You will provide your solution to the Data Lab by
editing the collection of functions in this source file.
 
CODING RULES:
 
  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code
  must conform to the following style:
 
  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;
 
      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }
 
  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>
   
  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.
 
  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
 
  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting an integer by more
     than the word size.
 
EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }
 
  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }
 
 
NOTES:
  1. Use the dlc (data lab checker) compiler (described in the handout) to
     check the legality of your solutions.
  2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
     that you are allowed to use for your implementation of the function.
     The max operator count is checked by dlc. Note that '=' is not
     counted; you may use as many of these as you want without penalty.
  3. Use the btest test harness to check your functions for correctness.
  4. The maximum number of ops for each function is given in the
     header comment for each function. If there are any inconsistencies
     between the maximum ops in the writeup and in this file, consider
     this file the authoritative source.
#endif
 
/*
 * STEP 3: Modify the following functions according the coding rules.
 *
 *   IMPORTANT. TO AVOID GRADING SURPRISES:
 *   1. Use the dlc compiler to check that your solutions conform
 *      to the coding rules.
 *   2. Use the btest test harness to check that your solutions produce
 *      the correct answers. Watch out for corner cases around Tmin and Tmax.
 */
/*
 * isZero - returns 1 if x == 0, and 0 otherwise
 *   Examples: isZero(5) = 0, isZero(0) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int isZero(int x) {
  return !x;
}
/*
 * 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);
 
}
/*
 * minusOne - return a value of -1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int minusOne(void) {
    // 0x00000000에서 0xFFFFFFFF로 바꿔주기
  return ~0;
}
/*
 * 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);
}
/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1<<(    31);
    // 0b0000 0000 0000 0001에서 0b1000 0000 0000 0000가 되기까지
}
/*
 * bitXor - x^y using only ~ and &
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
  return ~(~(~x&y) & ~(~y&x));
  //return ~( (~x&y) &  (~y&x) );
}
/*
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int evenBits(void) {
    int asdf=85; // 0b1010101을 뜻함.
    int barrrr =asdf | (asdf << 8)| (asdf<<16) | (asdf<<24);
    // 0b1010101에 1010101000000000, 101010100000...00000 ,... OR로 연산함
  return barrrr;
}
/*
 * 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&0x1) )+1;
}
/*
 * 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) {
    //printf("%d번 째 ",n) ;
    char genius;
//    genius = x >> ((n-1)<<3);
    genius = x >> ((n)<<3);
  return genius&0xFF; 
 
}
/*
 * 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));
}
/*
 * reverseBytes - reverse the bytes of x
 *   Example: reverseBytes(0x01020304) = 0x04030201
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 25
 *   Rating: 3
 */
int reverseBytes(int x) {
    //printf("0x%p의: \n",x);
    //return (((((x<<8|x>>24)<<8)|x>>16)<<8 )| (x>>8));
    int asdf = (x<<8| (x>>8&0xFF ) );
    //printf("0x%p\n",asdf);
    int barrrr = (asdf<<8| (x>>16&0xFF ) );
    //printf("0x%p\n",barrrr);
  
    asdf = (barrrr<<8| (x>>24&0xFF ) );
  
    //printf("0x%p\n",asdf);
  
    return asdf;
}
/*
 * 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) {
 
    int ifNotZero = (( ~((!(!x))&0x1) )+1) & y;
 
    int ifIsZero = ((~((!x)&0x1) )+1) & z;
  
  return ifNotZero|ifIsZero;
}
/*
 * bitMask - Generate a mask consisting of all 1's
 *   lowbit and highbit
 *   Examples: bitMask(5,3) = 0x38
    ==> 즉, 32개 비트 중에서 5번째 비트부터 3번째 비트까지 해당하는 비트들을 모두 1로 바꾼다는 의미
    ==> 0x38 = 0b 0000 0000 0011 1000
    ==> 예제 하나 더, h 9, l 2면 0x000003FC
    ==> 0b 0000 0011 1111 1100
 *   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) {
    int mask1 = ~(~0 << lowbit);
    int mask2 = ~0 << highbit;
    int mask3 = ~(1 << highbit);
 
    return ~(mask1 | (mask2 & mask3));
 
}
/*
 * 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)+1;
}
/*
 * sum3 - x+y+z using only a single '+'
 *   Example: sum3(3, 4, 5) = 12
 *   Legal ops: ! ~ & ^ | << >>
 *   Max ops: 16
 *   Rating: 3
 */
/* A helper routine to perform the addition.  Don't change this code */
static int sum(int x, int y) {
  return x+y;
}
int sum3(int x, int y, int z) {
 
  int word1 = (x^y) ^ z;
  int word2 = ( (x&y) | (x&z) | (y&z) ) << 1;
  /**************************************************************
     Fill in code below that computes values for word1 and word2
     without using any '+' operations
  ***************************************************************/
  /**************************************************************
     Don't change anything below here
  ***************************************************************/
  return sum(word1,word2);
}
/*
 * 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;
    int forPlus;
    int forMinus;
    int asdf;
    sign = (x>>31)&1<<31; // 양수면 00000000, 음수면 10000000
    forMinus = sign>>31; // 양수면 00000000, 음수면 11111111
    forPlus = ~forMinus; // 양수면 11111111, 음수면 00000000
  
    forMinus = forMinus&x; // 양수면 00000000, 음수면 x(SM형)
    forPlus = forPlus&x; // 양수면 x, 음수면 00000000
  
    forMinus = ~(forMinus+~0); // (2'c형일때 양/음을 바꾸는것, SM형일때 +sign(10000000)이랑 결합해 2's형으로 바꾸는것)
    asdf = forMinus+forPlus+sign;
  return asdf;
}
/*
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1 0이면 1, 0아니면 0
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int bang(int x) {
    int asdf = x >> 31; // 부호, -일 때 111111로 채워짐
    int barrrr = (~x + 1) >> 31; // 0000..00일 때 +1이면 오버플로인 것을 이용, +일 때 1111로 채워짐  
 
 
  return  (asdf | barrrr) + 1;
}
/*
 * abs - absolute value of x (except returns TMin for TMin)
 *   Example: abs(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int abs(int x) {
    int foo=x>>31; // 부호, 마찬가지로 -일 때만 11111..로 채워짐
    return (~foo & x) | (foo & (~x + 1));
 
}

bits.c

다운로드

 

보시다시피 테스트를 전부 통과한 답안입니다.

이 답안에서 다루는 함수: isZero, bitOr, bitAnd, minusOne, tmin, bitXor, copyLSB, getByte, isNotEqual, evenBits, isNonNegative, reverseBytes, sum3, conditional, bitMask, abs, bang, sm2tc 총 18개

 

참고자료:  

http://read.pudn.com/downloads143/sourcecode/windows/system/622852/bits.c__.htm 

https://github.com/cantora/cs2400-datalab/blob/master/bits.c
https://github.com/kywe665/ECEn-324/blob/master/lab1/bits.c
http://www.cs.northwestern.edu/~wms128/bits.c
http://mo0.belkanairforce.com/Lab1.txt
 

 

면책 조항:

답안은 제가 직접 작성했습니다. 하지만 저는 내용의 정확성을 보증하지 않습니다.

 

출처: http://blog.naver.com/PostView.nhn?blogId=treasure4me&logNo=220832214501