Logo CloudLunar

    CSAPP/Bits

    深入理解计算机系统 实验作业

    1. 实验目的:本次实验是对位操作级别的练习，本次报告是对实验中bits.c文件的再次说明，目的是帮助理解位级别的操作和表达以及培养同学们写代码之前先思考清楚思路的良好习惯，需要同学们认真完成
    2. 报告要求:本次报告需要同学们把对应实验中的函数逐一进行分析说明，写出实现的依据，也就是推理过程，可以是一个简单的数学证明，也可以是代码分析，根据实现中你的想法不同而异。请同学们耐心独立完成。


    显示/移除行号
    1. /*
    2.  * CS:APP Data Lab
    3.  *
    4.  * bits.c - Source file with your solutions to the Lab.
    5.  *          This is the file you will hand in to your instructor.
    6.  *
    7.  */
    8. #include <limits.h>
    9. #include <stdio.h>
    10. #include <stdlib.h>
    11. #include <time.h>
    12. #include "tests.h"
    13. /*
    14.  * Instructions to Students:
    15.  *
    16.  * STEP 1: Fill in the following struct with your identifying info.
    17.  */
    18. #if 0
    19. /*
    20.  * STEP 2: Read the following instructions carefully.
    21.  */
    22. You will provide your solution to the Data Lab by
    23. editing the collection of functions in this source file.
    24. CODING RULES:
    25.   Replace the "return" statement in each function with one
    26.   or more lines of C code that implements the function. Your code
    27.   must conform to the following style:
    28.   int Funct(arg1, arg2, ...) {
    29.       /* brief description of how your implementation works */
    30.       int var1 = Expr1;
    31.       ...
    32.       int varM = ExprM;
    33.       varJ = ExprJ;
    34.       ...
    35.       varN = ExprN;
    36.       return ExprR;
    37.   }
    38.   Each "Expr" is an expression using ONLY the following:
    39.   1. Integer constants 0 through 255 (0xFF), inclusive. You are
    40.       not allowed to use big constants such as 0xffffffff.
    41.   2. Function arguments and local variables (no global variables).
    42.   3. Unary integer operations ! ~
    43.   4. Binary integer operations & ^ | + << >>
    44.   Some of the problems restrict the set of allowed operators even further.
    45.   Each "Expr" may consist of multiple operators. You are not restricted to
    46.   one operator per line.
    47.   You are expressly forbidden to:
    48.   1. Use any control constructs such as if, do, while, for, switch, etc.
    49.   2. Define or use any macros.
    50.   3. Define any additional functions in this file.
    51.   4. Call any functions.
    52.   5. Use any other operations, such as &&, ||, -, or ?:
    53.   6. Use any form of casting.
    54.   You may assume that your machine:
    55.   1. Uses 2s complement, 32-bit representations of integers.
    56.   2. Performs right shifts arithmetically.
    57.   3. Has unpredictable behavior when shifting an integer by more
    58.      than the word size.
    59. EXAMPLES OF ACCEPTABLE CODING STYLE:
    60.   /*
    61.    * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
    62.    */
    63.   int pow2plus1(int x) {
    64.      /* exploit ability of shifts to compute powers of 2 */
    65.      return (1 << x) + 1;
    66.   }
    67.   /*
    68.    * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
    69.    */
    70.   int pow2plus4(int x) {
    71.      /* exploit ability of shifts to compute powers of 2 */
    72.      int result = (1 << x);
    73.      result += 4;
    74.      return result;
    75.   }
    76. #endif
    77. /*
    78.  * STEP 3: Modify the following functions according the coding rules.
    79.  *
    80.  */
    81. /* NO:1
    82.  * bitAnd - x&y using only ~ and |
    83.  *   Example: bitAnd(6, 5) = 4
    84.  *   Legal ops: ~ |
    85.  *   Max ops: 8
    86.  *   Rating: 1
    87.  */
    88. int bitAnd(int x, int y) {
    89.   return ~((~x)|(~y));
    90. }
    91. /* NO:2
    92.  * bitNor - ~(x|y) using only ~ and &
    93.  *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
    94.  *   Legal ops: ~ &
    95.  *   Max ops: 8
    96.  *   Rating: 1
    97.  */
    98. int bitNor(int x, int y) {
    99.   return (~x)&(~y);
    100. }
    101. /* NO:3
    102.  * copyLSB - set all bits of result to least significant bit of x
    103.  *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
    104.  *   Legal ops: ! ~ & ^ | + << >>
    105.  *   Max ops: 5
    106.  *   Rating: 2
    107.  */
    108. int copyLSB(int x) {
    109.   return (~0)+!(x&1);
    110.   #if 0
    111.     [Solution of Problem 3]
    112.     Using ~0 we can get an 0xFFFFFFFF;
    113.     If the LSB, which is the bit deciding whether the number is even or not, is equal to 1,
    114.        the number should be odd and the answer should be 0xFFFFFFFF(~0),
    115.        so we add nothing.
    116.     If the LSB is equal to 0,
    117.         the number should be even and the correct answer should be 0,
    118.         which is equal to 0xFFFFFFFF+1,
    119.         so we can add 1 to 0xFFFFFFF.
    120.     In order to figure out whether the number is odd or even,
    121.         we can use x%2, or x&1.
    122.     So the correct answer should be (~0)+!(x&1);
    123.     4 ops used.
    124.   #endif
    125. }
    126. /* NO:4
    127.  * evenBits - return word with all even-numbered bits set to 1
    128.  *   Legal ops: ! ~ & ^ | + << >>
    129.  *   Max ops: 8
    130.  *   Rating: 2
    131.  */
    132. int evenBits(void) {
    133.   int p=0x55;
    134.   p=(p<<8)+p;
    135.   p=(p<<16)+p;
    136.   return p;
    137.   #if 0
    138.     [Solution of Problem 4]
    139.     I think this solution is not so concise, but I do not have any better ideas.
    140.     Firstly,  we manually set a int p as 0x55(01010101 in binary).
    141.     Then, we double it by (p<<8)+p and get 0xAAAA.
    142.     Finally, we double it again and get 0x55, which is the answer we want.
    143.     4 ops used.
    144.   #endif
    145. }
    146. /* NO:5
    147.  * logicalShift - shift x to the right by n, using a logical shift
    148.  *   Can assume that 1 <= n <= 31
    149.  *   Examples: logicalShift(0x87654321,4) = 0x08765432
    150.  *   Legal ops: ~ & ^ | + << >>
    151.  *   Max ops: 16
    152.  *   Rating: 3
    153.  */
    154. int logicalShift(int x, int n) {
    155.   int p=(1<<31)&x;// Getting the sign bit.
    156.   int u=x^p;//Changing the sign bit
    157.   u>>=n;//Right move the u
    158.   p=(!!p)<<30>>n<<1;//Add back the sign bit
    159.   return u|p;
    160.   #if 0
    161.     [Solution of Problem 5]
    162.     Firstly, we can simply get the sign bit by BitAnd x and 0x40000000(1<<31).
    163.         After this operation, if the sign bit is 1, then set p to 0x40000000(1<<31).
    164.         Otherwise, the p will be 0;
    165.     Then, we can use u=x^p to get a number which is equal to p but the sign bit is set to 0.
    166.     Then, when shr u, the logical shifting result will be equal to the result of arithmetic one.
    167.     Finally we try to add the deleted sign bit back to new u. We need to shr the p logically, too.
    168.         This process is same as shl 1 by (31-n). However, the '-' is forbidden.
    169.         So we can <<31 and >>n. But it will reset the sign bit causing arithmetic shr.
    170.         So we divide this process into 3 parts: <<30, >>n, and <<1 finally. And get an acceptable answer.
    171.     10 ops used.
    172.   #endif
    173. }
    174. /* NO:6
    175.  * bang - Compute !x without using !
    176.  *   Examples: bang(3) = 0, bang(0) = 1
    177.  *   Legal ops: ~ & ^ | + << >>
    178.  *   Max ops: 12
    179.  *   Rating: 4
    180.  */
    181. int bang(int x) {
    182.   x=x|(x>>16);
    183.   x=x|(x>>8);
    184.   x=x|(x>>4);
    185.   x=x|(x>>2);
    186.   x=x|(x>>1);
    187.   return (~x)&1;
    188.   #if 0
    189.     [Solution of Problem 6]
    190.     Maybe the simple thought is to find whether a bit is non-zero bit by bit.
    191.     Because of limited operations, like problem 4, we need to cut the length of x half and half to reduce the steps.
    192.     So we using shr to cut half and | it with the original one. As the result, the last bit will be the OR result of all bits.
    193.     We can use &1 to get the last bit.
    194.     12 ops used.
    195.   #endif
    196. }
    197. /* NO:7
    198.  * leastBitPos - return a mask that marks the position of the
    199.  *               least significant 1 bit. If x == 0, return 0
    200.  *   Example: leastBitPos(96) = 0x20
    201.  *   Legal ops: ! ~ & ^ | + << >>
    202.  *   Max ops: 6
    203.  *   Rating: 4
    204.  */
    205. int leastBitPos(int x) {
    206.   return x&(~x+1);
    207.    #if 0
    208.     [Solution of Problem 7]
    209.     There is a feature about "plus one" in binary.
    210.         When we add 1 to a number in binary, we always reset all the non-zero bits after the first zero bit from the right.
    211.         Then we change that zero bit into one.
    212.     And this problem is similar. We need to change the first non-zero bit like the following process:
    213.         x=[XXXX100...00] -> y=[XXXX000...00] -> ans=x^y=[0000100...00]
    214.                ^                   ^                         ^
    215.     The most difficult part is how to get the y above. What we need is to borrow the "plus-one" process to finish this task.
    216.         We can using ~x as a springboard.
    217.         x=[XXXX100...00] -> ~x=[PPPP011...11] -> ~x+1=[PPPP100...00]
    218.                ^                    ^                      ^
    219.         It may hard to get y when we found we are here. But you may observe (~x+1)&x is the correct answer.
    220.     That is all.
    221.     4 ops used.
    222.   #endif
    223. }
    224. /* NO:8
    225.  * TMax - return maximum two's complement integer
    226.  *   Legal ops: ! ~ & ^ | + << >>
    227.  *   Max ops: 4
    228.  *   Rating: 1
    229.  */
    230. int tmax(void) {
    231.   return ~(1<<31);
    232.   #if 0
    233.     [Solution of Problem 8]
    234.     That is 01111..11, which is equal to ~10000..0;
    235.     2 ops used.
    236.   #endif
    237. }
    238. /* NO:9
    239.  * negate - return -x
    240.  *   Example: negate(1) = -1.
    241.  *   Legal ops: ! ~ & ^ | + << >>
    242.  *   Max ops: 5
    243.  *   Rating: 2
    244.  */
    245. int negate(int x) {
    246.   return (~x)+1;
    247.   #if 0
    248.     [Solution of Problem 9]
    249.     As we know, -p=~p+1;
    250.     For example, -1=[111...11]=[111...10]+1=~[000..01]+1=~(1)+1;
    251.                   1=[000...01]=[000...00]+1=~[111..11]+1=~(-1)+1;
    252.     //BTW: [...] means in binary.
    253.     2 ops used.
    254.   #endif
    255. }
    256. /* NO:10
    257.  * isPositive - return 1 if x > 0, return 0 otherwise
    258.  *   Example: isPositive(-1) = 0.
    259.  *   Legal ops: ! ~ & ^ | + << >>
    260.  *   Max ops: 8
    261.  *   Rating: 3
    262.  */
    263. int isPositive(int x) {
    264.   return (!!x)&(!(x>>31));
    265.   #if 0
    266.     [Solution of Problem 10]
    267.     Firstly, get the sign bit as problem 5;
    268.     Then using ! twice to change 0x40000000 to 1 while 0 to 0.
    269.     However, we need to check the an special situation that x==0.
    270.         0 is not positive, we need to & the answer given above with !!x to fix this.
    271.     6 ops used.
    272.   #endif
    273. }
    274. /* NO:11
    275.  * isNonNegative - return 1 if x >= 0, return 0 otherwise
    276.  *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
    277.  *   Legal ops: ! ~ & ^ | + << >>
    278.  *   Max ops: 6
    279.  *   Rating: 3
    280.  */
    281. int isNonNegative(int x) {
    282.   return !(x>>31);
    283.   #if 0
    284.     [Solution of Problem 11]
    285.     The same as the previous problem but we do not need to care about 0.
    286.     4 ops used.
    287.   #endif
    288. }
    289. /* NO:12
    290.  * sum3 - x+y+z using only a single '+'
    291.  *   Example: sum3(3, 4, 5) = 12
    292.  *   Legal ops: ! ~ & ^ | << >>
    293.  *   Max ops: 16
    294.  *   Rating: 3
    295.  */
    296. /* A helper routine to perform the addition.  Don't change this code */
    297. static int sum(int x, int y) {
    298.   return x+y;
    299. }
    300. int sum3(int x, int y, int z) {
    301.   int word1 = 0;
    302.   int word2 = 0;
    303.   /**************************************************************
    304.      Fill in code below that computes values for word1 and word2
    305.      without using any '+' operations
    306.   ***************************************************************/
    307.   word1=x^y^z;
    308.   word2=((x&y)|(y&z)|(z&x))<<1;
    309.   #if 0
    310.     [Solution of Problem 12]
    311.     I have read the book of Digital Logic about the adder. When we need to get c=a+b, we need to:
    312.         1.Half add: It is the same as c[i]+=a[i]^b[i];
    313.         2.Carry: if a[i]==b[i]==1, then c[i+1]++;
    314.     We always repeatly accomplish this two processes bit by bit, because the c[i] may be changed when carrying.
    315.     This problem provide us an opportunity to add. We may separate the two procedures into word1&2, then we can get the plus answer like:
    316.         word1=x^y;
    317.         word2=(x&y)<<1
    318.  
    319.     When there is 3 numbers needed to be added, it become confusing.
    320.     We should redefine the half-adder and the carrier. A table may help:
    321.         x[i]+y[i]+z[i]  word1[i]  word2[i+1]  TruthNumber
    322.               00            0        0          0
    323.               01            1        0          1
    324.               10            0        1          2
    325.               11            1        1          3
    326.     We know a fact that when we XOR some bool values, the answer is whether the number of truth in them is odd or even.
    327.         So the word1 should be x^y^z;
    328.     So word2? If more than 2 truths exist, the result should be 1. So we can enumerate all the situation and get:
    329.          word2=((x&y)|(y&z)|(z&x))<<1;
    330.     That is all.
    331.     8 ops used.
    332.   #endif
    333.   /**************************************************************
    334.      Don't change anything below here
    335.   ***************************************************************/
    336.   return sum(word1,word2);
    337. }
    338. /* NO:13
    339.  * addOK - Determine if can compute x+y without overflow
    340.  *   Example: addOK(0x80000000,0x80000000) = 0,
    341.  *            addOK(0x80000000,0x70000000) = 1,
    342.  *   Legal ops: ! ~ & ^ | + << >>
    343.  *   Max ops: 20
    344.  *   Rating: 3
    345.  */
    346. int addOK(int x, int y) {
    347.     int  p1=!(x>>31),p2=!(y>>31),p3=!((x+y)>>31);
    348.     return (p1^p2) | (!(p1^p3));
    349.     #if 0
    350.         [Solution of Problem 13]
    351.         Firstly, get the sign digits of x,y,x+y as p1, p2 and p3.
    352.         Then check p1, p2, p3 by:
    353.             if p1 != p2, then return 1;
    354.             else if p1,p2!=p3 return 0;
    355.             return 1;
    356.         We can use xor to accomplish the same effect, that is return (p1^p2) | (!(p1^p3));
    357.         11 ops used.
    358.     #endif
    359. }
    360. /* NO:14
    361.  * abs - absolute value of x (except returns TMin for TMin)
    362.  *   Example: cus_abs(-1) = 1.
    363.  *   Legal ops: ! ~ & ^ | + << >>
    364.  *   Max ops: 10
    365.  *   Rating: 4
    366.  */
    367. int cus_abs(int x) {
    368.   int condition=!(x>>31);
    369.   int value_when_true=x;
    370.   int value_when_false=(~x)+1;
    371.   int mask=condition+(~0);
    372.   return (~mask&value_when_true) | (mask&value_when_false);
    373.   #if 0
    374.     [Solution of Problem 14]
    375.     Amazingly, we find it intersting that we can accomplish a 'myIf' using 5 ops by:
    376.         int myIf(int condition=...,/*0 or 1*/,int value_when_true=...,int value_when_false...)
    377.         {
    378.             int mask=condition+(~0);
    379.             return (~mask&value_when_true) | (mask&value_when_false);
    380.             /*
    381.                 This uses a feature that bin[11111..11]+1=bin[000000..0].
    382.                 And we know[11111..11]&x=x while [00000..00]&x=0.
    383.             */
    384.         }
    385.     Using this "myIf" we all know this question is as same as:
    386.         myIf(x>0,x,-x);
    387.     We can simply use the solution of the previous problems to calculate x>0 and -x.
    388.     10 ops used.
    389.    #endif
    390. }
    391. /* NO:15
    392.  * isNonZero - Check whether x is nonzero using
    393.  *              the legal operators except !
    394.  *   Examples: isNonZero(3) = 1, isNonZero(0) = 0
    395.  *   Legal ops: ~ & ^ | + << >>
    396.  *   Max ops: 10
    397.  *   Rating: 4
    398.  */
    399. int isNonZero(int x) {
    400.     int n=~x+1;
    401.     return ((n>>31)|(x>>31))&1;
    402.   #if 0
    403.     [Solution of Problem 15]
    404.     I do not have any thoughts for a long time so I search the answer online.
    405.     As we know, only when x=0 can we get x==-x. When talking about "Two's complement", only when x=0 can we get the last bit of x is equal to -x.
    406.     So we can get the solution.
    407.     6 ops used.
    408.    #endif
    409. }
    410. int main(){
    411.     int a,n;
    412.     int i,Case;
    413.     int result = 0;
    414.     srand((unsigned)time(NULL));
    415.     //function NO:1
    416.     result=0;
    417.     Case=1;
    418.     for(i = 0; i < 1000000; i++)
    419.     {
    420.         int x = rand()-RAND_MAX/2;
    421.         int y = rand()-RAND_MAX/2;
    422.         if(bitAnd(x , y) != test_bitAnd(x,y))
    423.         {
    424.             result = 1;
    425.             printf("[Wrong! with %d != %d]\n",bitAnd(x , y), test_bitAnd(x,y));
    426.             break;
    427.         }
    428.     }
    429.     if(result != 0)
    430.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    431.     else
    432.         printf("NO.%d. All Passed!\n",Case);
    433.     //function: NO2
    434.     result=0;
    435.     Case=2;
    436.     for(i = 0; i < 1000000; i++)
    437.     {
    438.         int x = rand()-RAND_MAX/2;
    439.         int y = rand()-RAND_MAX/2;
    440.         if(bitNor(x , y) != test_bitNor(x,y))
    441.         {
    442.             result = 1;
    443.             printf("[Wrong! with %d != %d]\n",bitAnd(x , y), test_bitAnd(x,y));
    444.             break;
    445.         }
    446.     }
    447.     if(result != 0)
    448.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    449.     else
    450.         printf("NO.%d. All Passed!\n",Case);
    451.     //function: NO3
    452.     result=0;
    453.     Case=3;
    454.     for(i = 0; i < 1000000; i++)
    455.     {
    456.         int x = rand()-RAND_MAX/2;
    457.         if(copyLSB(x) != test_copyLSB(x))
    458.         {
    459.             result = 1;
    460.             printf("[Wrong! with %d != %d]\n",copyLSB(x), test_copyLSB(x));
    461.             break;
    462.         }
    463.     }
    464.     if(result != 0)
    465.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    466.     else
    467.         printf("NO.%d. All Passed!\n",Case);
    468.     //function: NO4
    469.     result=0;
    470.     Case=4;
    471.     for(i = 0; i < 1000000; i++)
    472.     {
    473.         int x = rand()-RAND_MAX/2;
    474.         int y = rand()-RAND_MAX/2;
    475.         if(evenBits() != test_evenBits())
    476.         {
    477.             result = 1;
    478.             printf("[Wrong! with %d != %d]\n",evenBits(), test_evenBits());
    479.             break;
    480.         }
    481.     }
    482.     if(result != 0)
    483.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    484.     else
    485.         printf("NO.%d. All Passed!\n",Case);
    486.     //function: NO5
    487.     result=0;
    488.     Case=5;
    489.     for(i = 0; i < 1000000; i++)
    490.     {
    491.         int x = rand()-RAND_MAX/2;
    492.         int y = rand()%31;
    493.         if(logicalShift(x , y) != test_logicalShift(x,y))
    494.         {
    495.             result = 1;
    496.             printf("[Wrong! with %d != %d]\n",logicalShift(x , y), test_logicalShift(x,y));
    497.             break;
    498.         }
    499.     }
    500.     if(result != 0)
    501.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    502.     else
    503.         printf("NO.%d. All Passed!\n",Case);
    504.     //function: NO6
    505.     result=0;
    506.     Case=6;
    507.     for(i = 0; i < 1000000; i++)
    508.     {
    509.         int x = rand()-RAND_MAX/2;
    510.         if(bang(x) != test_bang(x))
    511.         {
    512.             result = 1;
    513.             printf("[Wrong! with %d != %d]\n",bang(x), test_bang(x));
    514.             break;
    515.         }
    516.     }
    517.     if(result != 0)
    518.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    519.     else
    520.         printf("NO.%d. All Passed!\n",Case);
    521.     //function: NO7
    522.     result=0;
    523.     Case=7;
    524.     for(i = 0; i < 1000000; i++)
    525.     {
    526.         int x = rand()-RAND_MAX/2;
    527.         if(leastBitPos(x) != test_leastBitPos(x))
    528.         {
    529.             result = 1;
    530.             printf("[Wrong! with %d got %d != %d]\n",x,leastBitPos(x ), test_leastBitPos(x));
    531.             break;
    532.         }
    533.     }
    534.     if(result != 0)
    535.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    536.     else
    537.         printf("NO.%d. All Passed!\n",Case);
    538.     //function: NO8
    539.     result=0;
    540.     Case=8;
    541.     for(i = 0; i < 1000000; i++)
    542.     {
    543.         int x = rand()-RAND_MAX/2;
    544.         if( tmax() != test_tmax())
    545.         {
    546.             result = 1;
    547.             printf("[Wrong! with %d != %d]\n",tmax(), test_tmax());
    548.             break;
    549.         }
    550.     }
    551.     if(result != 0)
    552.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    553.     else
    554.         printf("NO.%d. All Passed!\n",Case);
    555.     //function: NO9
    556.     result=0;
    557.     Case=9;
    558.     for(i = 0; i < 1000000; i++)
    559.     {
    560.         int x = rand()-RAND_MAX/2;
    561.         if(negate(x ) != test_negate(x))
    562.         {
    563.             result = 1;
    564.             printf("[Wrong! with %d != %d]\n",negate(x ), test_negate(x));
    565.             break;
    566.         }
    567.     }
    568.     if(result != 0)
    569.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    570.     else
    571.         printf("NO.%d. All Passed!\n",Case);
    572.     //function: NO10
    573.     result=0;
    574.     Case=10;
    575.     for(i = 0; i < 1000000; i++)
    576.     {
    577.         int x = rand()-RAND_MAX/2;
    578.         if(isPositive(x) != test_isPositive(x))
    579.         {
    580.             result = 1;
    581.             printf("[Wrong! with %d got %d != %d]\n",x,isPositive(x), test_isPositive(x));
    582.             break;
    583.         }
    584.     }
    585.     if(result != 0)
    586.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    587.     else
    588.         printf("NO.%d. All Passed!\n",Case);
    589.     //function: NO11
    590.     result=0;
    591.     Case=11;
    592.     for(i = 0; i < 1000000; i++)
    593.     {
    594.         int x = rand()-RAND_MAX/2;
    595.         if(isNonNegative(x ) != test_isNonNegative(x))
    596.         {
    597.             result = 1;
    598.             printf("[Wrong! with %d != %d]\n",isNonNegative(x), test_isNonNegative(x));
    599.             break;
    600.         }
    601.     }
    602.     if(result != 0)
    603.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    604.     else
    605.         printf("NO.%d. All Passed!\n",Case);
    606.     //function: NO12
    607.     result=0;
    608.     Case=12;
    609.     for(i = 0; i < 1000000; i++)
    610.     {
    611.         int x = rand()-RAND_MAX/2;
    612.         int y = rand()-RAND_MAX/2;
    613.         int z = rand()-RAND_MAX/2;
    614.         if(sum3(x , y,z) != test_sum3(x,y,z))
    615.         {
    616.             result = 1;
    617.             printf("[Wrong! with %d != %d]\n",sum3(x , y,z), test_sum3(x,y,z));
    618.             break;
    619.         }
    620.     }
    621.     if(result != 0)
    622.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    623.     else
    624.         printf("NO.%d. All Passed!\n",Case);
    625.     //function: NO13
    626.     result=0;
    627.     Case=13;
    628.     for(i = 0; i < 1000000; i++)
    629.     {
    630.         int x = rand()-RAND_MAX/2;
    631.         int y = rand()-RAND_MAX/2;
    632.         if(addOK(x , y) != test_addOK(x,y))
    633.         {
    634.             result = 1;
    635.             printf("[Wrong! with %d != %d]\n",addOK(x , y), test_addOK(x,y));
    636.             break;
    637.         }
    638.     }
    639.     if(result != 0)
    640.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    641.     else
    642.         printf("NO.%d. All Passed!\n",Case);
    643.     //function: NO14
    644.     result=0;
    645.     Case=14;
    646.     for(i = 0; i < 1000000; i++)
    647.     {
    648.         int x = rand()-RAND_MAX/2;
    649.         int y = rand()-RAND_MAX/2;
    650.         if(cus_abs(x ) != test_abs(x))
    651.         {
    652.             result = 1;
    653.             printf("[Wrong! with %d != %d]\n",cus_abs(x ), test_abs(x));
    654.             break;
    655.         }
    656.     }
    657.     if(result != 0)
    658.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    659.     else
    660.         printf("NO.%d. All Passed!\n",Case);
    661.     //function: NO15
    662.     result=0;
    663.     Case=15;
    664.     for(i = 0; i < 1000000; i++)
    665.     {
    666.         int x = rand()-RAND_MAX/2;
    667.         int y = rand()-RAND_MAX/2;
    668.         if(isNonZero(x ) !=  test_isNonZero(x))
    669.         {
    670.             result = 1;
    671.             printf("[Wrong! with %d got %d != %d]\n",x,isNonZero(x ), test_isNonZero(x));
    672.             break;
    673.         }
    674.     }
    675.     if(result != 0)
    676.         printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
    677.     else
    678.         printf("NO.%d. All Passed!\n",Case);
    679.     return 0;
    680. }
    Tests.h代码已折叠
    展开折叠内容
    显示/移除行号
    1. /* Testing Code */
    2. #include <limits.h>
    3. int test_bitAnd(int x, int y)
    4. {
    5.   return x&y;
    6. }
    7. int test_bitNor(int x, int y)
    8. {
    9.   return ~(x|y);
    10. }
    11. int test_copyLSB(int x)
    12. {
    13.   return (x & 0x1) ? -1 : 0;
    14. }
    15. int test_evenBits(void) {
    16.   int result = 0;
    17.   int i;
    18.   for (i = 0; i < 32; i+=2)
    19.     result |= 1<<i;
    20.   return result;
    21. }
    22. int test_logicalShift(int x, int n) {
    23.   unsigned u = (unsigned) x;
    24.   unsigned shifted = u >> n;
    25.   return (int) shifted;
    26. }
    27.  
    28.  
    29.  
    30. int test_bang(int x)
    31. {
    32.   return !x;
    33. }
    34. int test_leastBitPos(int x) {
    35.   int mask = 1;
    36.   if (x == 0)
    37.     return 0;
    38.   while (!(mask & x)) {
    39.     mask = mask << 1;
    40.   }
    41.   return mask;
    42. }
    43. int test_tmax(void) {
    44.   return LONG_MAX;
    45. }
    46. int test_negate(int x) {
    47.   return -x;
    48. }
    49. int test_isPositive(int x) {
    50.   return x > 0;
    51. }
    52. int test_isNonNegative(int x) {
    53.   return x >= 0;
    54. }
    55. int test_sum3(int x, int y, int z)
    56. {
    57.   return x+y+z;
    58. }
    59. int test_addOK(int x, int y)
    60. {
    61.   int sum = x+y;
    62.   return !(x < 0 && y < 0 && sum >= 0) && !(x > 0 && y > 0 && sum <= 0);
    63. }
    64. int test_abs(int x) {
    65.   return (x < 0) ? -x : x;
    66. }
    67. int test_isNonZero(int x)
    68. {
    69.   return x!=0;
    70. }

    参考资料和拓展阅读

    1. http://www.cs.northwestern.edu/~wms128/bits.c
    取自“https://blog.CloudLunar.com/index.php?title=CSAPP/Bits&oldid=1371”
    分享ShareQQ空间新浪微博人人网一键分享TwitterFacebook

    著作权声明[编辑]

    关于[编辑]