fork download
copy 
  1. #include <stdio.h>
  2. #include <limits.h>
  3. /* 
  4.  * CS:APP Data Lab 
  5.  * 
  6.  * <Please put your name and userid here>
  7.  * 
  8.  * bits.c - Source file with your solutions to the Lab.
  9.  *          This is the file you will hand in to your instructor.
  10.  *
  11.  * WARNING: Do not include the <stdio.h> header; it confuses the dlc
  12.  * compiler. You can still use printf for debugging without including
  13.  * <stdio.h>, although you might get a compiler warning. In general,
  14.  * it's not good practice to ignore compiler warnings, but in this
  15.  * case it's OK.  
  16.  */
  17.  
  18. #if 0
  19. /*
  20.  * Instructions to Students:
  21.  *
  22.  * STEP 1: Read the following instructions carefully.
  23.  */
  24.  
  25. You will provide your solution to the Data Lab by
  26. editing the collection of functions in this source file.
  27.  
  28. INTEGER CODING RULES:
  29.  
  30.   Replace the "return" statement in each function with one
  31.   or more lines of C code that implements the function. Your code 
  32.   must conform to the following style:
  33.  
  34.   int Funct(arg1, arg2, ...) {
  35.       /* brief description of how your implementation works */
  36.       int var1 = Expr1;
  37.       ...
  38.       int varM = ExprM;
  39.  
  40.       varJ = ExprJ;
  41.       ...
  42.       varN = ExprN;
  43.       return ExprR;
  44.   }
  45.  
  46.   Each "Expr" is an expression using ONLY the following:
  47.   1. Integer constants 0 through 255 (0xFF), inclusive. You are
  48.       not allowed to use big constants such as 0xffffffff.
  49.   2. Function arguments and local variables (no global variables).
  50.   3. Unary integer operations ! ~
  51.   4. Binary integer operations & ^ | + << >>
  52.  
  53.   Some of the problems restrict the set of allowed operators even further.
  54.   Each "Expr" may consist of multiple operators. You are not restricted to
  55.   one operator per line.
  56.  
  57.   You are expressly forbidden to:
  58.   1. Use any control constructs such as if, do, while, for, switch, etc.
  59.   2. Define or use any macros.
  60.   3. Define any additional functions in this file.
  61.   4. Call any functions.
  62.   5. Use any other operations, such as &&, ||, -, or ?:
  63.   6. Use any form of casting.
  64.   7. Use any data type other than int.  This implies that you
  65.      cannot use arrays, structs, or unions.
  66.  
  67.  
  68.   You may assume that your machine:
  69.   1. Uses 2s complement, 32-bit representations of integers.
  70.   2. Performs right shifts arithmetically.
  71.   3. Has unpredictable behavior when shifting an integer by more
  72.      than the word size.
  73.  
  74. EXAMPLES OF ACCEPTABLE CODING STYLE:
  75.   /*
  76.    * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
  77.    */
  78.   int pow2plus1(int x) {
  79.      /* exploit ability of shifts to compute powers of 2 */
  80.      return (1 << x) + 1;
  81.   }
  82.  
  83.   /*
  84.    * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
  85.    */
  86.   int pow2plus4(int x) {
  87.      /* exploit ability of shifts to compute powers of 2 */
  88.      int result = (1 << x);
  89.      result += 4;
  90.      return result;
  91.   }
  92.  
  93. FLOATING POINT CODING RULES
  94.  
  95. For the problems that require you to implent floating-point operations,
  96. the coding rules are less strict.  You are allowed to use looping and
  97. conditional control.  You are allowed to use both ints and unsigneds.
  98. You can use arbitrary integer and unsigned constants.
  99.  
  100. You are expressly forbidden to:
  101.   1. Define or use any macros.
  102.   2. Define any additional functions in this file.
  103.   3. Call any functions.
  104.   4. Use any form of casting.
  105.   5. Use any data type other than int or unsigned.  This means that you
  106.      cannot use arrays, structs, or unions.
  107.   6. Use any floating point data types, operations, or constants.
  108.  
  109.  
  110. NOTES:
  111.   1. Use the dlc (data lab checker) compiler (described in the handout) to 
  112.      check the legality of your solutions.
  113.   2. Each function has a maximum number of operators (! ~ & ^ | + << >>)
  114.      that you are allowed to use for your implementation of the function. 
  115.      The max operator count is checked by dlc. Note that '=' is not 
  116.      counted; you may use as many of these as you want without penalty.
  117.   3. Use the btest test harness to check your functions for correctness.
  118.   4. Use the BDD checker to formally verify your functions
  119.   5. The maximum number of ops for each function is given in the
  120.      header comment for each function. If there are any inconsistencies 
  121.      between the maximum ops in the writeup and in this file, consider
  122.      this file the authoritative source.
  123.  
  124. /*
  125.  * STEP 2: Modify the following functions according the coding rules.
  126.  * 
  127.  *   IMPORTANT. TO AVOID GRADING SURPRISES:
  128.  *   1. Use the dlc compiler to check that your solutions conform
  129.  *      to the coding rules.
  130.  *   2. Use the BDD checker to formally verify that your solutions produce 
  131.  *      the correct answers.
  132.  */
  133.  
  134.  
  135. #endif
  136. /* 
  137.  * bang - Compute !x without using !
  138.  *   Examples: bang(3) = 0, bang(0) = 1
  139.  *   Legal ops: ~ & ^ | + << >>
  140.  *   Max ops: 12
  141.  *   Rating: 4 
  142.  */
  143. int bang(int x) {
  144.  return ((x | (~x+1)) >> 31) + 1;
  145. }
  146. /*
  147.  * bitCount - returns count of number of 1's in word
  148.  *   Examples: bitCount(5) = 2, bitCount(7) = 3
  149.  *   Legal ops: ! ~ & ^ | + << >>
  150.  *   Max ops: 40
  151.  *   Rating: 4
  152.  */
  153. int bitCount(int x) {
  154. #define const1 0x55
  155. #define const2 0x33
  156. #define const3 0x0F
  157. #define const4 0xFF
  158.     int y = x;
  159. 	int iconst1 = const1; // this needs to be 0x55555555
  160. 	int iconst2 = const2; // this needs to be 0x33333333
  161. 	int iconst3 = const3; // this needs to be 0x0F0F0F0F
  162. 	int iconst4 = 0;      // this needs to be 0x00FF00FF
  163. 	int iconst5 = 0; // this needs to be 0x0000FFFF
  164. 	int negx;
  165.  
  166.  
  167. 	iconst1 =  (iconst1 <<8) | const1;
  168. 	iconst1 = (iconst1 << 16) | iconst1; // now iconst1 is 0x55555555
  169.  
  170. 	iconst2  = (iconst2 <<8) | const2;
  171. 	iconst2 = (iconst2 << 16) | iconst2; // now iconst2 is 0x33333333
  172.  
  173. 	iconst3 = (iconst3 << 8) | const3;
  174. 	iconst3 = (iconst3 << 16) | iconst3; // now iconst3 is 0x0F0F0F0F
  175.  
  176. 	iconst4 = ((((iconst4 << 8) | const4) << 16 | const4));  // now iconst4 is 0x00FF00FF
  177. 	iconst5 =  ((iconst5 <<16) | const4)<<8 | const4;  // now iconst5 0x0000FFFF
  178.  
  179. 	// Basically, if we take a 2 bit number the number can be 11, 10, 01 and 00
  180. 	// to count the number of 1s in this 2 bit number- 
  181. 	// right shift by 1- 01; 01; 00; 00
  182. 	// subtract from the original number- (11 - 01) = 2; (10 - 01) = 1; (01- 00) = 1; 00-00 = 0
  183. 	// you will get the number of 1s. 
  184.  
  185. 	// so we will start with: 
  186. 	// y = y - (( y >> 1) & 0x55555555
  187. 	// Now, each 2 bit will have the correct count of number of bits in those 2 bits. 
  188. 	// as soon as we right shift by 1, the higher order bit of the 2 bits should be masked out
  189. 	// since it is always zero in a 2 bit arithmetic. so, we mask it out with the pattern 0101 01 01
  190. 	// which becomes 0x55555555
  191.  
  192. 	negx = ~((y>>1) & iconst1) + 1;  // taking 2's complement of (y >>1) & iconst1
  193. 	y = y + negx;  
  194.  
  195. 	// now every adjascent 2 bits have the number of bits in the original numbers' 2 bits.
  196. 	// we have to start adding the adjascent 2 bits. 
  197. 	//  y = (y & 0x33333333) + ((y >>2) & 0x33333333)
  198. 	// here we right shift the value by 2, and add to the original value
  199. 	// however the higher order 2 bits of the 4 bits we just accumulated have to be masked out.
  200. 	// so we and it with the pattern 0011 0011 0011 etc- which is 0x33333333
  201.  
  202. 	y = ((y >>2) & iconst2) + (y & iconst2);
  203.  
  204. 	// at this time every 4 bits will have one of the following values:
  205. 	// 0000 or 0001 or 0011 or 0100 - the number of 1s in each 4 bits of the original number.
  206.  
  207. 	// if we do  y + (y >>4)- then each lower 4 bits will have the right numbers. 
  208. 	// but upper 4 bits of the result is irrelevant. so, we can mask out upper 4 bits with
  209. 	// anding with 0F.
  210. 	// so this is what we do:
  211. 	// y = ( y + (y >> 4)) & 0x0F0F0F0F
  212.  
  213. 	y = ((y>>4) + y) & iconst3;
  214.  
  215. 	// now all 4 bytes will have the proper count of the 1s in the original bytes.
  216. 	// The bytes will have the following possible values:
  217. 	// 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08
  218. 	// we can add the adjascent bytes by adding the number right shifted by 8 to the number.
  219. 	// however, need to mask out the odd numbered bytes .
  220. 	// so we do 
  221. 	// y = ( y + ( y >> 8)) & 0x00ff00ff
  222.  
  223. 	y = ((y >>8) +y) & iconst4;
  224.  
  225. 	// now the two halfs of the word (first two bytes and last two bytes) have the count
  226. 	// we need to add them. it is done by: adding the number right shifted by 16 to the number.
  227. 	// of course we need to mask out the first 2 bytes of the word.
  228. 	// so it is done by:
  229. 	// y = ( y + (y >>16)) & 0x0000FFFF;
  230.  
  231. 	y = ((y >>16) +y) & iconst5;
  232.  
  233.  
  234. 	return y; 
  235. }
  236. /* 
  237.  * bitOr - x|y using only ~ and & 
  238.  *   Example: bitOr(6, 5) = 7
  239.  *   Legal ops: ~ &
  240.  *   Max ops: 8
  241.  *   Rating: 1
  242.  */
  243. int bitOr(int x, int y) {
  244. 	int num1 = ~x;
  245. 	int num2 = ~y;
  246. 	return (~(num1 & num2));
  247.  
  248. }
  249. /*
  250.  * bitRepeat - repeat x's low-order n bits until word is full.
  251.  *   Can assume that 1 <= n <= 32.
  252.  *   Examples: bitRepeat(1, 1) = -1
  253.  *             bitRepeat(7, 4) = 0x77777777
  254.  *             bitRepeat(0x13f, 8) = 0x3f3f3f3f
  255.  *             bitRepeat(0xfffe02, 9) = 0x10080402
  256.  *             bitRepeat(-559038737, 31) = -559038737
  257.  *             bitRepeat(-559038737, 32) = -559038737
  258.  *   Legal ops: int and unsigned ! ~ & ^ | + - * / % << >>
  259.  *             (This is more general than the usual integer coding rules.)
  260.  *   Max ops: 40
  261.  *   Rating: 4
  262.  */
  263.  
  264.  
  265.  
  266. int bitRepeat1(int x, int n) {
  267.  
  268. 	int castval;
  269. 	/** mask off all the bits to the left of nth bit into repeat **/
  270. 	int neg_one = -1;
  271. 	int repeat = ~(neg_one << n) & x;
  272.  
  273. 	//nMax = all 1s if n== 32 . else nMax is all 0s 
  274.  
  275. 	int nMax = -!(n^32);
  276.  
  277.  
  278. 	/* first shift- 1 X */
  279.  
  280. 	repeat = (repeat << n) | repeat;
  281.  
  282.  
  283. 	/** second shift - 2X- overflow bits come into play */
  284.  
  285. 	n = n* 2;
  286.  
  287.         /* set castval to -1 iff n<32 and 0 otherwise */
  288.  
  289. 	castval = ~((31-n)>>31);
  290.  
  291. 	repeat = repeat | ((repeat << n) &  castval);
  292.  
  293.  
  294. 	/* third shift- 4 X - overflow check still applies */
  295. 	n = n* 2;
  296.  
  297. 	castval = ~((31-n)>>31);
  298.  
  299. 	repeat = repeat | ((repeat << n) &  castval);
  300.  
  301. 	/* fourth shift 8 X  overflow check will continue */
  302. 	n = n* 2;
  303.  
  304. 	castval = ~((31-n)>>31);
  305.  
  306. 	repeat = repeat | ((repeat << n) &  castval);
  307.  
  308. 	/* fifth and LASt shift 16 X overflow check will continue */
  309. 	n = n* 2;
  310.  
  311. 	castval = ~((31-n)>>31);
  312.  
  313. 	repeat = repeat | ((repeat << n) &  castval);
  314.  
  315.  
  316. 	return (repeat & ~nMax) | (x & nMax); 
  317. }
  318. int bitRepeat( int x, int n){
  319.  
  320. 	int x1 = !(n/32);
  321. 	int x2 = ! (n/16);
  322. 	int x3 = ! (n/8);
  323. 	int x4 = ! (n/4);
  324. 	int x5 = ! (n/2);
  325.  
  326. 	unsigned int a = (x <<(32-n));
  327. 	unsigned int rpt = a >> (32-n);
  328.  
  329. 	rpt = rpt << (n* x1) | (rpt *x1);
  330. 	rpt = rpt << ((n*2) *x2) | (rpt *x2);
  331. 	rpt = rpt << ((n*4) * x3) | (rpt *x3);
  332. 	rpt = rpt << ((n*8) * x4) | (rpt *x4);
  333. 	rpt = rpt << ((n*16) * x5) | (rpt *x5);
  334.  
  335. 	return rpt;
  336. }
  337. /* 
  338.  * fitsBits - return 1 if x can be represented as an 
  339.  *  n-bit, two's complement integer.
  340.  *   1 <= n <= 32
  341.  *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
  342.  *   Legal ops: ! ~ & ^ | + << >>
  343.  *   Max ops: 15
  344.  *   Rating: 2
  345.  */
  346. int fitsBits(int x, int n) {
  347. 	/* if nth bit of the X (counting from right) is 1, it won't fit */
  348.     int rval, hob_remain;
  349. 	/* computing remaining high order bits beyond the "n" shift bits */
  350. 	hob_remain = 32 + (~n + 1); // taking 2s complement of n to make it -n and adding it to 32
  351. 	/* propagating the MSB of X to the all the bits to the left of X */
  352. 	rval = (x<<hob_remain) >> hob_remain; // left shifting by remaining HOB bits gets the MSB of x to MSB of int; then arithmetic shift.
  353. 	return !(rval ^ x); // this actually returns rval == x;
  354. }
  355. /* 
  356.  * getByte - Extract byte n from word x
  357.  *   Bytes numbered from 0 (LSB) to 3 (MSB)
  358.  *   Examples: getByte(0x12345678,1) = 0x56
  359.  *   Legal ops: ! ~ & ^ | + << >>
  360.  *   Max ops: 6
  361.  *   Rating: 2
  362.  */
  363. int getByte(int x, int n) {
  364.   return (x >> (n <<3)) & 0xFF;
  365. }
  366. /* 
  367.  * isLessOrEqual - if x <= y  then return 1, else return 0 
  368.  *   Example: isLessOrEqual(4,5) = 1.
  369.  *   Legal ops: ! ~ & ^ | + << >>
  370.  *   Max ops: 24
  371.  *   Rating: 3
  372.  */
  373. int isLessOrEqual(int x, int y) {
  374. 	int diff_sgn = !(x>>31)^!(y>>31);      //is 1 when signs are different
  375. 	int a = diff_sgn & (x>>31);            //diff signs and x is neg, gives 1
  376. 	int b = !diff_sgn & !((y+(~x+1))>>31); //same signs and difference is pos or = 0, gives 1
  377. 	int f = a | b;
  378. 	return f;
  379. }
  380. /* 
  381.  * isPositive - return 1 if x > 0, return 0 otherwise 
  382.  *   Example: isPositive(-1) = 0.
  383.  *   Legal ops: ! ~ & ^ | + << >>
  384.  *   Max ops: 8
  385.  *   Rating: 3
  386.  */
  387. int isPositive(int x) {
  388.  return (!(x >>31)) & ~(!(x^0));
  389. }
  390. /* 
  391.  * logicalShift - shift x to the right by n, using a logical shift
  392.  *   Can assume that 0 <= n <= 31
  393.  *   Examples: logicalShift(0x87654321,4) = 0x08765432
  394.  *   Legal ops: ! ~ & ^ | + << >>
  395.  *   Max ops: 20
  396.  *   Rating: 3 
  397.  */
  398. int logicalShift(int x, int n) {
  399.  
  400. 	/* Doing an arithmetic shift and zeroing out all the bits to the left of previous MSB */
  401.  
  402.   return (x >> n) & ~(((0x1 << 31) >> n) << 1);
  403. }
  404. /* 
  405.  * tmin - return minimum two's complement integer 
  406.  *   Legal ops: ! ~ & ^ | + << >>
  407.  *   Max ops: 4
  408.  *   Rating: 1
  409.  */
  410. int tmin(void) {
  411.   return 0x01 <<31;
  412. }
  413.  
  414. int main(void) {
  415. 	// your code goes here
  416. 	printf("Bang of 9 is %d\n", bang(9));
  417. 	printf("Bang of INT_MIN is %d\n", bang(INT_MIN));
  418. 	printf("Bang of INT_MAX is %d\n", bang(INT_MAX));
  419. 	printf("Bang of 0 is %d\n", bang(0));
  420. 	printf("Bitcount of 9 is %d\n", bitCount(9));
  421. 	printf("Bitcount of INT_MIN is %d\n", bitCount(INT_MIN));
  422. 	printf("Bitcount of INT_MAX is %d\n", bitCount(INT_MAX));
  423. 	printf("Bitcount of -1 is %d\n", bitCount(-1));
  424.  
  425. 	printf("bitwise or of 6 and 5 is %d\n", bitOr(6,5));
  426. 	printf("bitwise or of INT_MIN and INT_MAX is %d\n", bitOr(INT_MIN,INT_MAX));
  427.  
  428. 	printf("bitrepeat of 7 & 4 = %8x \n", bitRepeat(7,4));
  429. 	printf("bitrepeat of 1 & 1 = %8x \n", bitRepeat(1,1));
  430. 	printf("bitrepeat of 0x13f & 8 = %8x \n", bitRepeat(0x13f,8));
  431. 	printf("bitrepeat of 0xfffe02 & 9 = %8x \n", bitRepeat(0x00fffe02,9));
  432. 	printf("bitrepeat of -559038737 & 31 = %d \n", bitRepeat(-559038737,31));
  433. 	printf("bitrepeat of -559038737 & 32 = %d \n", bitRepeat(-559038737,32));
  434. 	printf("bitrepeat of INT_MIN & 32 =%8x\n", bitRepeat (INT_MIN, 32));
  435. 	printf("bitrepeat of 0x50c9e87e & 0x3 is %8x\n", bitRepeat (0x50c9e87e, 0x3));
  436. 	printf("bitrepeat of digital 0x50c9e87e & 0x3 is %8x\n", bitRepeat (1355409534, 0x3));
  437.  
  438.  
  439.  
  440. 	printf("fitsBits of 5 & 3 = %d\n", fitsBits(5,3));
  441. 	printf("fitsBits of -4 &3 = %d\n", fitsBits(-4, 3));
  442.  
  443. 	printf("getByte of 0x12345678, 1 %08x\n", getByte(0x12345678,1));
  444. 	printf("getByte of 0x87654321, 3 %08x\n", getByte(0x87654321,3));
  445. 	printf("isLessorEqual of 4, 5 is = %d\n", isLessOrEqual(4,5));
  446. 	printf("isLessorEqual of INT_MIN, INT_MAX is = %d\n", isLessOrEqual(INT_MIN,INT_MAX));
  447. 	printf("isLessorEqual of INT_MAX, INT_MIN is = %d\n", isLessOrEqual(INT_MAX,INT_MIN));
  448. 	printf("isLessorEqual of INT_MAX, INT_MIN+1 is = %d\n", isLessOrEqual(INT_MAX,INT_MIN+1));
  449. 	printf("isLessorEqual of INT_MIN, INT_MIN is = %d\n", isLessOrEqual(INT_MIN,INT_MIN));
  450. 	printf("isLessorEqual of INT_MAX, INT_MAX is = %d\n", isLessOrEqual(INT_MAX,INT_MAX));
  451.  
  452. 	printf("IsPositive (-1) = %d\n", isPositive(-1));
  453. 	printf("IsPositive (INT_MIN) = %d\n", isPositive(INT_MIN));
  454. 	printf("IsPositive (0) = %d\n", isPositive(0));
  455. 	printf("IsPositive 0x7ffffffe is %d\n", isPositive(0x7ffffffe));
  456.  
  457. 	printf("logical shift (0x87654321,4) = %08x\n", logicalShift(0x87654321,4));
  458.  
  459. 	printf("tmin value = %08x  In Decimal %d\n", tmin(), tmin());
  460.  
  461. 	return 0;
  462. }
  463.  
  464.  
Success #stdin #stdout 0s 10320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Bang of 9 is 0
Bang of INT_MIN is 0
Bang of INT_MAX is 0
Bang of 0 is 1
Bitcount of 9 is 2
Bitcount of INT_MIN is 1
Bitcount of INT_MAX is 31
Bitcount of -1 is 32
bitwise or of 6 and 5 is 7
bitwise or of INT_MIN and INT_MAX is -1
bitrepeat of 7 & 4 = 77777777 
bitrepeat of 1 & 1 = ffffffff 
bitrepeat of 0x13f & 8 = 3f3f3f3f 
bitrepeat of 0xfffe02 & 9 = 10080402 
bitrepeat of -559038737 & 31 = -559038737 
bitrepeat of -559038737 & 32 = -559038737 
bitrepeat of INT_MIN & 32 =80000000
bitrepeat of 0x50c9e87e & 0x3 is b6db6db6
bitrepeat of digital 0x50c9e87e & 0x3 is b6db6db6
fitsBits of 5 & 3 = 0
fitsBits of -4 &3 = 1
getByte of 0x12345678, 1 00000056
getByte of 0x87654321, 3 00000087
isLessorEqual of 4, 5 is = 1
isLessorEqual of INT_MIN, INT_MAX is = 1
isLessorEqual of INT_MAX, INT_MIN is = 0
isLessorEqual of INT_MAX, INT_MIN+1 is = 0
isLessorEqual of INT_MIN, INT_MIN is = 1
isLessorEqual of INT_MAX, INT_MAX is = 1
IsPositive (-1) = 0
IsPositive (INT_MIN) = 0
IsPositive (0) = 0
IsPositive 0x7ffffffe is 1
logical shift (0x87654321,4) = 08765432
tmin value = 80000000  In Decimal -2147483648
https://ideone.com/C2aw9l
language:
C (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!