1.txt

bit operations 2007 version in C

chihoy:1:bits.c [chihoy, datalab] [Sat Sep 15 18:10:36 2007]
   1  /* 
   2   * CS:APP Data Lab 
   3   * 
   4   * <Please put your name and userid here>
   5   * 
   6   * bits.c - Source file with your solutions to the Lab.
   7   *          This is the file you will hand in to your instructor.
   8   *
   9   * WARNING: Do not include the <stdio.h> header; it confuses the dlc
  10   * compiler. You can still use printf for debugging without including
  11   * <stdio.h>, although you might get a compiler warning. In general,
  12   * it's not good practice to ignore compiler warnings, but in this
  13   * case it's OK.  
  14   */
  15  
  16  #if 0
  17  /*
  18   * Instructions to Students:
  19   *
  20   * STEP 1: Read the following instructions carefully.
  21   */
  22  
  23  You will provide your solution to the Data Lab by
  24  editing the collection of functions in this source file.
  25  
  26  INTEGER CODING RULES:
  27   
  28    Replace the "return" statement in each function with one
  29    or more lines of C code that implements the function. Your code 
  30    must conform to the following style:
  31   
  32    int Funct(arg1, arg2, ...) {
  33        /* brief description of how your implementation works */
  34        int var1 = Expr1;
  35        ...
  36        int varM = ExprM;
  37  
  38        varJ = ExprJ;
  39        ...
  40        varN = ExprN;
  41        return ExprR;
  42    }
  43  
  44    Each "Expr" is an expression using ONLY the following:
  45    1. Integer constants 0 through 255 (0xFF), inclusive. You are
  46        not allowed to use big constants such as 0xffffffff.
  47    2. Function arguments and local variables (no global variables).
  48    3. Unary integer operations ! ~
  49    4. Binary integer operations & ^ | + << >>
  50      
  51    Some of the problems restrict the set of allowed operators even further.
  52    Each "Expr" may consist of multiple operators. You are not restricted to
  53    one operator per line.
  54  
  55    You are expressly forbidden to:
  56    1. Use any control constructs such as if, do, while, for, switch, etc.
  57    2. Define or use any macros.
  58    3. Define any additional functions in this file.
  59    4. Call any functions.
  60    5. Use any other operations, such as &&, ||, -, or ?:
  61    6. Use any form of casting.
  62    7. Use any data type other than int.  This implies that you
  63       cannot use arrays, structs, or unions.
  64  
  65   
  66    You may assume that your machine:
  67    1. Uses 2s complement, 32-bit representations of integers.
  68    2. Performs right shifts arithmetically.
  69    3. Has unpredictable behavior when shifting an integer by more
  70       than the word size.
  71  
  72  EXAMPLES OF ACCEPTABLE CODING STYLE:
  73    /*
  74     * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
  75     */
  76    int pow2plus1(int x) {
  77       /* exploit ability of shifts to compute powers of 2 */
  78       return (1 << x) + 1;
  79    }
  80  
  81    /*
  82     * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
  83     */
  84    int pow2plus4(int x) {
  85       /* exploit ability of shifts to compute powers of 2 */
  86       int result = (1 << x);
  87       result += 4;
  88       return result;
  89    }
  90  
  91  FLOATING POINT CODING RULES
  92  
  93  For the problems that require you to implent floating-point operations,
  94  the coding rules are less strict.  You are allowed to use looping and
  95  conditional control.  You are allowed to use both ints and unsigneds.
  96  You can use arbitrary integer and unsigned constants.
  97  
  98  You are expressly forbidden to:
  99    1. Define or use any macros.
 100    2. Define any additional functions in this file.
 101    3. Call any functions.
 102    4. Use any form of casting.
 103    5. Use any data type other than int or unsigned.  This means that you
 104       cannot use arrays, structs, or unions.
 105    6. Use any floating point data types, operations, or constants.
 106  
 107  
 108  NOTES:
 109    1. Use the dlc (data lab checker) compiler (described in the handout) to 
 110       check the legality of your solutions.
 111    2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
 112       that you are allowed to use for your implementation of the function. 
 113       The max operator count is checked by dlc. Note that '=' is not 
 114       counted; you may use as many of these as you want without penalty.
 115    3. Use the btest test harness to check your functions for correctness.
 116    4. Use the BDD checker to formally verify your functions
 117    5. The maximum number of ops for each function is given in the
 118       header comment for each function. If there are any inconsistencies 
 119       between the maximum ops in the writeup and in this file, consider
 120       this file the authoritative source.
 121  
 122  /*
 123   * STEP 2: Modify the following functions according the coding rules.
 124   * 
 125   *   IMPORTANT. TO AVOID GRADING SURPRISES:
 126   *   1. Use the dlc compiler to check that your solutions conform
 127   *      to the coding rules.
 128   *   2. Use the BDD checker to formally verify that your solutions produce 
 129   *      the correct answers.
 130   */
 131  
 132  
 133  #endif
 134  /* 
 135   * bitNor - ~(x|y) using only ~ and & 
 136   *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 137   *   Legal ops: ~ &
 138   *   Max ops: 8
 139   *   Rating: 1
 140   */
 141  int bitNor(int x, int y){
 142  
 143         // Use De Morgan's Law
 144         return (~x)&(~y);
 145  
 146  }
 147  /* 
 148   * copyLSB - set all bits of result to least significant bit of x
 149   *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 150   *   Legal ops: ! ~ & ^ | + << >>
 151   *   Max ops: 5
 152   *   Rating: 2
 153   */
 154  int copyLSB(int x) {
 155  
 156    // move the least significant bit to the most left bit, and use arithmetic right shift to copy the LSB
 157    return (x<<31)>>31;
 158  
 159  }
 160  /* 
 161   * isEqual - return 1 if x == y, and 0 otherwise 
 162   *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 163   *   Legal ops: ! ~ & ^ | + << >>
 164   *   Max ops: 5
 165   *   Rating: 2
 166   */
 167  int isEqual(int x, int y) {
 168  
 169    /* compare x and y using xor -> if they have the same bits then all the bits are 0, otherwise there will be at least one
 170     * using !, negate the true/false state
 171     */
 172    return !(x^y);
 173  
 174  }
 175  /* 
 176   * bitMask - Generate a mask consisting of all 1's 
 177   *   lowbit and highbit
 178   *   Examples: bitMask(5,3) = 0x38
 179   *   Assume 0 <= lowbit <= 31, and 0 <= highbit <= 31
 180   *   If lowbit > highbit, then mask should be all 0's
 181   *   Legal ops: ! ~ & ^ | + << >>
 182   *   Max ops: 16
 183   *   Rating: 3
 184   */
 185  int bitMask(int highbit, int lowbit) {
 186  
 187    int x,y,negate_0;
 188  
 189    negate_0 = ~0;
 190  
 191    // firstly, cover 0s with 1s from the LSB to highbit position
 192    x = negate_0;
 193    x = x<<(highbit+1);
 194    x = ~x;
 195  
 196    // for another binary number, cover 0s with 1s from the lowbit position to the MSB
 197    y = negate_0;
 198    y = y<<lowbit;
 199  
 200    // overlap the two binary numbers above and return 1s which are shared commonly
 201    return x&y;
 202  
 203  }
 204  /*
 205   * bitCount - returns count of number of 1's in word
 206   *   Examples: bitCount(5) = 2, bitCount(7) = 3
 207   *   Legal ops: ! ~ & ^ | + << >>
 208   *   Max ops: 40
 209   *   Rating: 4
 210   */
 211  int bitCount(int x) {
 212    
 213    int bitMask_1,bitMask_2,bitMask_3,bitMask_4,bitMask_5,a_1,a_2,a_3,a_4,a_5;
 214  
 215    // Set up the bitMasks which are corresponding to:
 216    // bitMask_1 = 01010101010101010101010101010101
 217    // bitMask_2 = 00110011001100110011001100110011
 218    // bitMask_3 = 00001111000011110000111100001111
 219    // bitMask_4 = 00000000111111110000000011111111
 220    // bitMask_5 = 00000000000000001111111111111111
 221  
 222    bitMask_1 = 0x55;
 223    bitMask_1 += (bitMask_1<<8);
 224    bitMask_1 += (bitMask_1<<16);
 225    bitMask_2 = 0x33;
 226    bitMask_2 += (bitMask_2<<8);
 227    bitMask_2 += (bitMask_2<<16);
 228    bitMask_3 = 0x0f;
 229    bitMask_3 += (bitMask_3<<8);
 230    bitMask_3 += (bitMask_3<<16);
 231    bitMask_4 = 0xff;
 232    bitMask_4 += (bitMask_4<<16);
 233    bitMask_5 = 0xff;
 234    bitMask_5 += (bitMask_4<<8);
 235  
 236    // Seperate 32 bits into 2 bits and count how many bits in each 2 bits and add them together
 237    a_1 = (x&bitMask_1) + ((x>>1)&bitMask_1);
 238  
 239    // Seperate 32 bits into 4 bits and count how many bits in each 4 bits and add them together
 240    a_2 = (a_1&bitMask_2) + ((a_1>>2)&bitMask_2);
 241  
 242    // Seperate 32 bits into 8 bits and count how many bits in each 8 bits and add them together
 243    a_3 = (a_2&bitMask_3) + ((a_2>>4)&bitMask_3);
 244  
 245    // Seperate 32 bits into 16 bits and count how many bits in each 16 bits and add them together
 246    a_4 = (a_3&bitMask_4) + ((a_3>>8)&bitMask_4);
 247  
 248    // Count how many bits in this newly updated 32 bits
 249    a_5 = (a_4&bitMask_5) + ((a_4>>16)&bitMask_5);
 250    
 251    return a_5;
 252  
 253  }
 254  /* 
 255   * TMax - return maximum two's complement integer 
 256   *   Legal ops: ! ~ & ^ | + << >>
 257   *   Max ops: 4
 258   *   Rating: 1
 259   */
 260  int tmax(void) {
 261  
 262    // move 1 to MSB with 0s in other positions, and negate it
 263    return ~((~0)<<31);
 264  
 265  }
 266  /* 
 267   * isNonNegative - return 1 if x >= 0, return 0 otherwise 
 268   *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
 269   *   Legal ops: ! ~ & ^ | + << >>
 270   *   Max ops: 6
 271   *   Rating: 3
 272   */
 273  int isNonNegative(int x) {
 274  
 275    // copy MSB and check whether it's 1 or 0
 276    return !(x>>31);
 277  
 278  }
 279  /* 
 280   * addOK - Determine if can compute x+y without overflow
 281   *   Example: addOK(0x80000000,0x80000000) = 0,
 282   *            addOK(0x80000000,0x70000000) = 1, 
 283   *   Legal ops: ! ~ & ^ | + << >>
 284   *   Max ops: 20
 285   *   Rating: 3
 286   */
 287  int addOK(int x, int y) {
 288    
 289    int case_1,case_2,sign_x,sign_y,sign_xpy;
 290  
 291    sign_x = x>>31;
 292    sign_y = y>>31;
 293    sign_xpy = (x+y)>>31;