제1차 실험

문제와 해답은 모두 코드에 있다.
4

/*
 * 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.
 *
 */
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "tests.h"
/*
 * Instructions to Students:
 *
 * STEP 1: Fill in the following struct with your identifying info.
 */

#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;
  }
#endif

/*
 * STEP 3: Modify the following functions according the coding rules.
 *
 */
/* NO: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));
}

/* NO:2
 * 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);
}
/* NO:3
 * 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;
}
/* NO:4
 * evenBits - return word with all even-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int evenBits(void) {
  int x=0x55;
  int result=0;
  result|=x;
  result|=x<<8;
  result|=x<<16;
  result|=x<<24;
  return result;
}
/* NO:5
 * 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 (~((1<<31)>>(n-1)))&(x>>n);
}
/* NO:6
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int bang(int x) {
  x|=x>>16;
  x|=x>>8;
  x|=x>>4;
  x|=x>>2;
  x|=x>>1;
  return (~x)&1;
}
/* NO:7
 * 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: 4
 */
int leastBitPos(int x) {
  return ((~x)+1)&x;
}
/* NO:8
 * TMax - return maximum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
  int x=~(1<<31);
  return x;
}
/* NO:9
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return (~x)+1;
}
/* NO:10
 * 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);
}
/* NO:11
 * 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);
}
/* NO:12
 * 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 = 0;
  int word2 = 0;
  /**************************************************************
     Fill in code below that computes values for word1 and word2
     without using any '+' operations
  ***************************************************************/
  word1=(x^y)^z;
  word2=((x&y&z)|((~word1)&(x|y|z)))<<1;
  /**************************************************************
     Don't change anything below here
  ***************************************************************/
  return sum(word1,word2);
}
/* NO:13
 * 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 t=x+y;
  int sx=x>>31;
  int sy=y>>31;
  int st=t>>31;
  return !((~(sx^sy))&(sx^st));
}
/* NO:14
 * 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 sx=x>>31;
  return (x&(~sx))|(((~x)+1)&sx);
}
/* NO:15
 * 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)+1)^x)|x)>>31)&1;
}

알이 아픈 실험 보고서,wps를 사용하지 않을 것
함수 분석
1. int bitAnd(int x, int y);
함수 구현:
int bitAnd (int x, int y) {
  return ~((~x) | (~y));
}
함수 분석:
데모건의 법칙에 따르면 ~(x&y)=(~x)|(~y)그래서: x&y=~(~x)|(~y))
 
2. int bitNor (int x, int y);
함수 구현:
Int bitNor(int x,int y){
return (~x)&(~y);
}
함수 분석:
데모건의 법칙에 의하면 ~(x|y)=(~x) & (~y)
3. Int copyLSB(int x);
함수 구현:
Int copyLSB(int x){
return (x<<31)>>31;
}
함수 분석: 산술 오른쪽 이동만 주의하면 됩니다
4.Int evenBits(int x);
함수 구현:
Int evenBits(int x){
 int x=0x55;
 Int result=0;
 result|=x;
 result|=x<<8;
 result|=x<<16;
 result|=x<<24;
 return result;
}
함수 분석: 0x55는 01010101, 각각 왼쪽으로 0(이동하지 않음), 8,16,24위에서
1,2,3,4 바이트는 모두 01010101, 즉 모든 짝수 바이트는 1이다
5.Int logicalShift(int x,int n);
 Int logicalShift(int x,int n){
   return (~((1<<31)>>(n-1)))&(x>>n);
 }
함수 분석: 1<<31 발생은 최고 1이고 나머지 비트는 모두 0의 수이다. 그 값은 오른쪽으로 n-1위 이동하고 원래 x를 덮어쓰지 않으며 산술 오른쪽으로 이동하는 고위 보충 1의 마스크를 덮어쓰지 않는다. 다시 x>>n과 비교하면 된다.
    6.int bang(int x);
 int bang(int x) {
  x|=x>>16;
  x|=x>>8;
  x|=x>>4;
  x|=x>>2;
  x|=x>>1;
  return (~x)&1;
}
함수 분석: 먼저 한 개의 수가 1만 있으면 0으로 돌아가고 모두 0으로 1로 돌아가야 한다. 그러면 자연스럽게 한 개의 위상이나 한 개의 위상이 있거나 31번을 조작해야 하기 때문에 반으로 접는 방법을 생각해서 처음으로 16위를 옮겼다. 그러면 앞의 16위의 1은 뒤의 16위와 앞의 16위의 1이 병존하는 것과 같다. 이것은 연산 순서를 바꾸고 결합율을 사용해서 순서대로 유추하는 것과 같다.
8자리 2진수를 예로 들면 이 숫자는 a1, a2, a3, a4, a5, a6, a7, a8이라고 가정한다.
처음 4자리 이동: (15)(26)(37)(48)
두 번째 위치 이동: (15)(37)(26)(48)
마지막: (15)(37)(26)(48))
(편의를 위해 i로ai를 대표한다)
7.int leastBitPos(int x);
int leastBitPos(int x) {
  return ((~x)+1)&x;
}
함수 분석: 최저 위치를 i로 설정하면 0에서 i-1은 모두 0이고 ~x는 x위와 반대로 0에서 i-1은 모두 1이다. 그러면 (~x)+1에 있어 0에서 i-1은 모두 0이고 i위는 1이다. i+1에서 31위는 x와 반대로 x와 직접 i위를 얻을 수 있는 마스크는 x와 같다.
8.int tmax(void);
int tmax(void) {
  return ~(1<<31);
}
함수 분석: INTMAX는 32위가 0이고 나머지는 1이라는 숫자입니다.
9.int negate(int x);
int negate(int x) {
  return (~x)+1;
}
함수 분석, 즉 부호화, 즉 반가1
10.int isPostive(int x);
int isPositive(int x) {
  return (!(x>>31))&(!!x);
}
함수 분석: 가장 높은 위치가 기호 위치이기 때문에!(x>>31) 1시, x>=0, 0시, 0시, x<0;지금 x=0의 상황을 배제하려면 x!=만 있습니다0시,!!x=1이므로 두 가지 양식을 함께 사용하면 된다
11.int isNonNegative(int x);
int isNonNegative(int x) {
  return !(x>>31);
}
함수 분석:동상
12.static int sum(int x, int y);
static int sum(int x, int y) {
  return x+y;
}
int sum3(int x, int y, int z) {
  int word1 = 0;
  int word2 = 0;
      word1=(x^y)^z;
      word2=((x&y&z)|((~word1)&(x|y|z)))<<1;
      return sum(word1,word2);
}
함수 분석: 사고방식은 먼저 진위가 없는 덧셈을 한 번 한 다음에sum로 진위를 덧붙이는 것이다.
x^y^z는 비진위 가법에 해당한다. 다음에 어떤 분에 대해 진위를 분석한다. x, y,z 중 두 개 또는 세 개가 있을 때 진위가 발생한다. 이때 상응하는 위치를 1로 하고 마지막에 한 자리를 왼쪽으로 옮기면 된다.x&y&z는 3개가 모두 1인 경우 ~word1은 0 또는 2개1이고 x|y|z는 적어도 1개가 있는 경우 진위를 판단합니다.
13.int addOK(int x, int y);
int addOK(int x, int y) {
  int t=x+y;
  int sx=x>>31;
  int sy=y>>31;
  int st=t>>31;
  return !((~(sx^sy))&(sx^st));
}
함수 분석: sx는 x의 기호 위치로 32자리를 채우는 것을 나타낸다. y,z와 마찬가지로 함수는 x, y는 같은 번호이지만 x+y와 x가 다른 번호일 때 0을 되돌려야 한다. 그렇지 않으면 1을 되돌려야 한다.
14.int abs(int x);
int abs(int x) {
  int sx=x>>31;
  return (x&(~sx))|(((~x)+1)&sx);
}
함수 분석: 함수는 x>0 또는 x=TMIN일 때 x를 되돌려주고 x<0(x!=TMIN)일 때 -x(즉 반가1)를 되돌려줍니다. 그러면 기호 위치로 둘만 되돌려받는 것을 제어해야 합니다.
15.int isNonZero(int x)
int isNonZero(int x) {
  return (((((~x)+1)^x)|x)>>31)&1;
}
함수 분석: (((~x)+1)^x)|x는 가장 낮은 1위부터 32위까지 모두 1이고 나머지는 모두 0의 수(0은 전체 0)를 얻으면 31위를 오른쪽으로 옮겨 가장 높은 위치와 1을 맞히면 된다.