SSD06 Exercise02 个人解答

题目 写道

Data Lab: Manipulating Bits

Introduction

The purpose of this assignment is to become more familiar with bit-level representations and manipulations. You'll do this by solving a series of programming ``puzzles.'' Many of these puzzles are quite artificial, but you'll find yourself thinking much more about bits in working your way through them and you will learn a lot about how computers represent integer data.

Getting Started

Download and unzip dlab-handout.zip to a directory in which you plan to do your work. This will cause the following files to be unpacked into the directory:

bits.c	The data puzzles that you will solve. This is the file you will be modifying and handing in.
dlab.vcproj	Project file.
README	Helpful information about the lab
btest.c btest.h decl.c test.c getopt.c bits.h getopt.h tailor.h	The test driver and its helper file

以上是Open the dlab.vcproj project from VC++ and you are ready to begin solving your puzzles. You can add this project to a pre-existing (or new) VC++.Net Solution.

Your Task

The only file you will be modifying and turning in is bits.c . Looking at bits.c you'll notice a C structure called info into which you should insert your name and login ID. Do this right away so you don't forget, as the driver will not run without it.

The bits.c file also contains a skeleton for each of the 10 programming puzzles. Your assignment is to complete each function skeleton using only straightline code (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operators. Specifically, you are only allowed to use the following eight operators:

 ! ~ & ^ | + << >>

A few of the functions further restrict this list. See the comments in bits.c for detailed rules and a discussion of the desired coding style.

The enclosed dlab.vcproj project will help you compile your bits.c file, along with the other helper functions, and link them all together to form the executable driver program btest.exe . The btest.exe driver program allows you to evaluate the functional correctness of your code. Every time you modify one of the puzzles in bits.c , you can check its correctness by rebuilding and rerunning btest.exe .

Puzzles

The following table describes the 10 puzzles that you will be solving in bits.c . The ``Rating'' field gives the difficulty rating (the number of points) for the puzzle, and the ``Max ops'' field gives the maximum number of operators you are allowed to use to implement each function.

Name	Description	Rating	Max Ops
bitAnd(x,y)	Returns (x & y) using only ~ and |	1	8
bitOr(x,y)	Returns (x | y) using only ~ and &	1	8
isZero(x)	Returns 1 if x == 0 and 0 otherwise	1	2
minusOne()	Returns a value of -1	1	2
tmax()	Returns the maximum two's complement integer	1	4
bitXor(x, y)	Returns (x ^ y) using only ~ and &	2	14
getByte(x)	Extract byte number n from word x	2	14
isEqual(x,y)	Returns 1 if x == y , and 0 otherwise	2	5
negate(x)	Returns -x	2	5
isPositive(x)	Returns 1 if x > 0 , and 0 otherwise	3	8

• Function bitAnd computes the And function. That is, when applied to arguments x and y , it returns (x & y) . You may only use the operators ~ and | .
• Similarly, function bitOr computes the Or function. That is, when applied to arguments x and y , it returns (x | y) . You may only use the operators ~ and & .
• A predicate is a function that returns either true or false. Function isZero is a predicate that returns a value of 1 (true) if x is equal to zero. Otherwise, it returns a value of 0 (false).
• Function minusOne takes no arguments and always returns a value of -1, without using the minus operator.
• Function tmax , which also takes no arguments, returns the largest positive two's complement number.
• Function bitXor should duplicate the behavior of the bitwise Xor operation ^ , using only the operations & and ~ .
• Function getByte extracts a byte from a word and returns that byte. The bytes within a word are ordered from 0 (least significant) to 3 (most significant). For example, getByte(0x12345678,1) = 0x56
• Function isEqual compares x to y for equality, returning 1 (true) if x == y and 0 (false) otherwise.
• Function negate computes and returns the negative of its input argument x , without using the minus operator.
• Function isPositive is a predicate that returns 1 (true) if its input argument is greater than zero. Otherwise, it returns 0 (false).

Evaluation

Your score will be computed out of a maximum of 30 points based on the following distribution:

16	Correctness of code as reported by btest.exe (no credit for a puzzle if your instructor determines that you have used an illegal operator).
10	Performance of code, based on number of operators used in each function (maximum of 1 point per puzzle).
4	Style points, based on your instructor's subjective evaluation of the quality of your solutions and your comments.

The 10 puzzles you must solve have been given a difficulty rating between 1 and 3, such that their weighted sum totals to 16. Your instructor will evaluate your functions using the same btest.exe driver that you are using. You will get full credit for a puzzle if it passes all of the tests performed by btest.exe , half credit if it fails one test, and no credit otherwise. You receive no credit if you use an illegal operator for your solution, so pay close attention to the list of allowed operators for each puzzle in bits.c .

Regarding performance, our main concern at this point in the course is that you can get the right answer. However, we want to instill in you a sense of keeping things as short and simple as you can. Thus, for each function we've established a maximum number of operators that you are allowed to use for each function. This limit is very generous and is designed only to catch egregiously inefficient solutions. You will receive one point for each function that satisfies the operator limit.

Finally, we've reserved four points for a subjective evaluation of the style of your solutions and your commenting. Your solutions should be as clean and straightforward as possible. Your comments should be informative, but they need not be extensive.

Advice

• Read the file README for information on running the btest.exe program.
• You'll find it helpful to work through the functions one at a time, testing each one as you go. You can use the -f flag to instruct btest.exe to test only a single function. For example, "btest.exe -f bitAnd ".
• The "-g " flag is very handy for producing a concise summary of your correctness results. For example, "btest -g ".
• btest.exe is a console application, so you'll need to run it from the Windows command line. On a Windows 2000 system, you can find this at "Start->Accessories->Command Prompt". If you try to run it using "Start->Run.." instead, you won't see any of the output.

Hand In Instructions

Before submitting your solution:

• Make sure you have included your identifying information in your file bits.c .
• Remove any extraneous print statements that you might have included for debugging.

 题目考察的是大量的数据转换与处理，我们在答题之前必需具备一些必要的基础知识。

 

一、基本概念：

1. !在C中，非零则返回0,否则返回1   
   
2.  ~数据项每一位都取反 
   
3. &两数据项各位取AND 
   
4. ^两数据各个位取异或
5.  |两数据项各位取或
6.  +两数据项相加
7. <<数据bit上左移
8. >>数据bit上右移

二、计算机中数据的存储

1. 数据在计算机中是以比特为基本单位进行存储的
2. 整形数据都是以补码形式存储的
   

三、解题分析

为了论述的方便，我直接将论述放在代码注释中，最后会简单总结一下。

/* 
 * bits.c - Source file with your solutions to the Lab.
 *          This is the file you will hand in to your instructor.
 */

#include "btest.h"
#include <limits.h>

/*
 * Instructions to Students:
 *
 * STEP 1: Fill in the following struct with your identifying info.
 */
info_struct info =
{
   /* Replace with your full name */
   "xxxxxxxxxxxxxxx",
   /* Replace with your login ID */
   "xxxxxxxxxxxxxxx",
};

#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 AND HINTS:
  1. Each function has a maximum number of operators (! ~ & ^ | + << >>)
     that you are allowed to use for your implementation of the function. 
     The max operator count will be checked by your instructor. 
     Note that '=' is not counted; you may use as many of these as you 
     want without penalty.
  2. Use the btest test harness to check your functions for correctness.
#endif

/*
 * STEP 3: Modify the following functions according the coding rules.
 */



/* 
 * bitAnd - x&y using only ~ and | 
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y) {
  // x&y = ~ ( (~x) | (~y) )
  //具体分析： x&y = ~~(x&y)=~(~x | ~y)
  int a = ~x;
  int b = ~y;
  int c = a|b;
  int d = ~c;
  return d;
}



/* 
 * bitOr - x|y using only ~ and & 
 *   Example: bitOr(6, 5) = 7
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitOr(int x, int y) {
  //x|y=~( (~x) & (~y) )
  //具体分析：x|y=~~(x|y)=~(~x & ~y)
  int a = ~x;
  int b= ~y;
  int c = a&b;
  int d = ~c;

  return d;
}


/*
 * 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) {
  //异或操作的特点是不同才为一，也就是说如果这个数据要为零，则其和0的数据表示应该完全相同，那么得到的
  //异或值应该为0,如果不为零则表示不是零。
  int a = 0;
  return !(x^a);
}






/* 
 * minusOne - return a value of -1 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 2
 *   Rating: 1
 */
int minusOne(void) {
  //-1的补码表示是：0xFFFFFFFF,其对应的取反数据为0x00000000刚好为0
  return ~0;

}






/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
  //补码最大的数据为0x7FFFFFFF(=2^32-1)
  //对应的数据取反数据为0x80000000(=2^32)
  return ~(1<<31);

}




/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
  //x^y=~~(x^y)=~~( (x& ~y) | ( ~x &y) ) = ~ ( ~( x & ~y) & ~( ~x & y)  ) 
  int a = ~(x&(~y));
  int b = ~((~x)&y);
  int c = a&b;
  int d = ~c;
  return d;

}






/* 
 * 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) {
  //利用&运算截取其中的数据就好了，我在这里是调整ff到合适的byte位置然后截取最后在对结果右移。整体上还是
  //比较麻烦的。另外就是最节将数据右移并在底端截取合适的数据。
  int a = 0x000000ff;
  int p = n<<3;
  int b = a<<p;
  int c = x&b;
  int d = c>>p;
  return d;

}


/* 
 * isEqual - return 1 if x == y, and 0 otherwise 
 *   Examples: isEqual(5,5) = 1, isEqual(4,5) = 0
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int isEqual(int x, int y) {
  //isZero是一个特例
  return !(x^y);

}


/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  // 取反有一个规律： 正数K取反的结果是 - (K + 1)
  return ~x+1;

}



/* 
 * isPositive - return 1 if x > 0, return 0 otherwise 
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x) {
  //一个正数的符号位是最高的第32位，我们需要获得这个的数据。但是0不是正数，所以需要排除。
  return !((x>>31)&1 | !x);

}

在这里要明白：

1. 数据的底层存储是补码形式，但是这样是对负数有影响

2. 正数K--> ~K = -(K+1)证明：

现在设一个数 i ，在这里我们假设这个数据没有符号位，即永远表示的是一个正数，如果想表示负数则直接写成 (-)i.现在我们有 i ，则 (-)i 的数据存储应该是 A=(-)(~i + 1).当计算机看到A时通过(-)知道其为一个负数,然后需要解析出它表示的数字：(-)  ~(A-1) = (-)i

但是我们现在将一个普通的数据a：

当a为正数时, a = i , ~a = (-) ~i=-a-1

当a为负数时, a = (-)i, ~a = ~i = ~i + 1 - 1 = ~i - 1 + 1 = -a + 1

综上所述：得到结论

3. 关于用Ruby解本题

参见

Ruby的运算符!和整形数据类型小结

 

评论

2 楼 qianjigui 2008-12-02  

标准解答是：
/* 
  * 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;
} 
其实思路是一样的，只是我的比较麻烦一些。
错误原因：如果符号位是一的话右边统一补零。
如果是我的解答的话：getByte(0xffffffff,3)=0xffffffff
所以最后还需要再做一次与运算：
/*  
* 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) {  
  //利用&运算截取其中的数据就好了，我在这里是调整ff到合适的byte位置然后截取最后在对结果右移。整体上还是  
  //比较麻烦的。另外就是最节将数据右移并在底端截取合适的数据。  
  int a = 0x000000ff;  
  int p = n<<3;  
  int b = a<<p;  
  int c = x&b;  
  int d = c>>p;  
  return d&a;  
 
}  

1 楼 qianjigui 2008-12-01  

Your score on this question is:  90.00

Feedback:
   Feedback for Puzzles (v2.0)
Total Score: 90/100

    * Operation Puzzles
      Score: 23/26

          o bitAnd(x,y)
            Score: 2/2

          o bitOr(x,y)
            Score: 2/2

          o isZero(x)
            Score: 2/2

          o minusOne()
            Score: 2/2

          o tmax()
            Score: 2/2

          o bitXor(x, y)
            Score: 3/3

          o getByte(x, n)
            Score: 0/3
            getByte not correctly implemented.

          o isEqual(x,y)
            Score: 3/3

          o negate(x)
            Score: 3/3

          o isPositive(x)
            Score: 4/4

    * Style
      Score: 4/4