CloudLunar
/*
* 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 (~0)+!(x&1);
#if 0
[Solution of Problem 3]
Using ~0 we can get an 0xFFFFFFFF;
If the LSB, which is the bit deciding whether the number is even or not, is equal to 1,
the number should be odd and the answer should be 0xFFFFFFFF(~0),
so we add nothing.
If the LSB is equal to 0,
the number should be even and the correct answer should be 0,
which is equal to 0xFFFFFFFF+1,
so we can add 1 to 0xFFFFFFF.
In order to figure out whether the number is odd or even,
we can use x%2, or x&1.
So the correct answer should be (~0)+!(x&1);
4 ops used.
#endif
}
/* NO:4
* evenBits - return word with all even-numbered bits set to 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 8
* Rating: 2
*/
int evenBits(void) {
int p=0x55;
p=(p<<8)+p;
p=(p<<16)+p;
return p;
#if 0
[Solution of Problem 4]
I think this solution is not so concise, but I do not have any better ideas.
Firstly, we manually set a int p as 0x55(01010101 in binary).
Then, we double it by (p<<8)+p and get 0xAAAA.
Finally, we double it again and get 0x55, which is the answer we want.
4 ops used.
#endif
}
/* 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) {
int p=(1<<31)&x;// Getting the sign bit.
int u=x^p;//Changing the sign bit
u>>=n;//Right move the u
p=(!!p)<<30>>n<<1;//Add back the sign bit
return u|p;
#if 0
[Solution of Problem 5]
Firstly, we can simply get the sign bit by BitAnd x and 0x40000000(1<<31).
After this operation, if the sign bit is 1, then set p to 0x40000000(1<<31).
Otherwise, the p will be 0;
Then, we can use u=x^p to get a number which is equal to p but the sign bit is set to 0.
Then, when shr u, the logical shifting result will be equal to the result of arithmetic one.
Finally we try to add the deleted sign bit back to new u. We need to shr the p logically, too.
This process is same as shl 1 by (31-n). However, the '-' is forbidden.
So we can <<31 and >>n. But it will reset the sign bit causing arithmetic shr.
So we divide this process into 3 parts: <<30, >>n, and <<1 finally. And get an acceptable answer.
10 ops used.
#endif
}
/* 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|(x>>16);
x=x|(x>>8);
x=x|(x>>4);
x=x|(x>>2);
x=x|(x>>1);
return (~x)&1;
#if 0
[Solution of Problem 6]
Maybe the simple thought is to find whether a bit is non-zero bit by bit.
Because of limited operations, like problem 4, we need to cut the length of x half and half to reduce the steps.
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.
We can use &1 to get the last bit.
12 ops used.
#endif
}
/* 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&(~x+1);
#if 0
[Solution of Problem 7]
There is a feature about "plus one" in binary.
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.
Then we change that zero bit into one.
And this problem is similar. We need to change the first non-zero bit like the following process:
x=[XXXX100...00] -> y=[XXXX000...00] -> ans=x^y=[0000100...00]
^ ^ ^
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.
We can using ~x as a springboard.
x=[XXXX100...00] -> ~x=[PPPP011...11] -> ~x+1=[PPPP100...00]
^ ^ ^
It may hard to get y when we found we are here. But you may observe (~x+1)&x is the correct answer.
That is all.
4 ops used.
#endif
}
/* NO:8
* TMax - return maximum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmax(void) {
return ~(1<<31);
#if 0
[Solution of Problem 8]
That is 01111..11, which is equal to ~10000..0;
2 ops used.
#endif
}
/* NO:9
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return (~x)+1;
#if 0
[Solution of Problem 9]
As we know, -p=~p+1;
For example, -1=[111...11]=[111...10]+1=~[000..01]+1=~(1)+1;
1=[000...01]=[000...00]+1=~[111..11]+1=~(-1)+1;
//BTW: [...] means in binary.
2 ops used.
#endif
}
/* 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)&(!(x>>31));
#if 0
[Solution of Problem 10]
Firstly, get the sign bit as problem 5;
Then using ! twice to change 0x40000000 to 1 while 0 to 0.
However, we need to check the an special situation that x==0.
0 is not positive, we need to & the answer given above with !!x to fix this.
6 ops used.
#endif
}
/* 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);
#if 0
[Solution of Problem 11]
The same as the previous problem but we do not need to care about 0.
4 ops used.
#endif
}
/* 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)|(y&z)|(z&x))<<1;
#if 0
[Solution of Problem 12]
I have read the book of Digital Logic about the adder. When we need to get c=a+b, we need to:
1.Half add: It is the same as c[i]+=a[i]^b[i];
2.Carry: if a[i]==b[i]==1, then c[i+1]++;
We always repeatly accomplish this two processes bit by bit, because the c[i] may be changed when carrying.
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:
word1=x^y;
word2=(x&y)<<1
When there is 3 numbers needed to be added, it become confusing.
We should redefine the half-adder and the carrier. A table may help:
x[i]+y[i]+z[i] word1[i] word2[i+1] TruthNumber
00 0 0 0
01 1 0 1
10 0 1 2
11 1 1 3
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.
So the word1 should be x^y^z;
So word2? If more than 2 truths exist, the result should be 1. So we can enumerate all the situation and get:
word2=((x&y)|(y&z)|(z&x))<<1;
That is all.
8 ops used.
#endif
/**************************************************************
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 p1=!(x>>31),p2=!(y>>31),p3=!((x+y)>>31);
return (p1^p2) | (!(p1^p3));
#if 0
[Solution of Problem 13]
Firstly, get the sign digits of x,y,x+y as p1, p2 and p3.
Then check p1, p2, p3 by:
if p1 != p2, then return 1;
else if p1,p2!=p3 return 0;
return 1;
We can use xor to accomplish the same effect, that is return (p1^p2) | (!(p1^p3));
11 ops used.
#endif
}
/* 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 condition=!(x>>31);
int value_when_true=x;
int value_when_false=(~x)+1;
int mask=condition+(~0);
return (mask&value_when_true) | ((~mask)&value_when_false);
#if 0
[Solution of Problem 14]
Amazingly, we find it intersting that we can accomplish a 'myIf' using 5 ops by:
int myIf(int condition=...,/*0 or 1*/,int value_when_true=...,int value_when_false...)
{
int mask=condition+(~0);
return (mask&value_when_true) | (~mask&value_when_false);
/*
This uses a feature that bin[11111..11]+1=bin[000000..0].
And we know[11111..11]&x=x while [00000..00]&x=0.
*/
}
Using this "myIf" we all know this question is as same as:
myIf(x>0,x,-x);
We can simply use the solution of the previous problems to calculate x>0 and -x.
10 ops used.
#endif
}
/* 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) {
int n=~x+1;
return ((n>>31)|(x>>31))&1;
#if 0
[Solution of Problem 15]
I do not have any thoughts for a long time so I search the answer online.
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.
So we can get the solution.
6 ops used.
#endif
}
int main(){
int a,n;
int i,Case;
int result = 0;
srand((unsigned)time(NULL));
//function NO:1
result=0;
Case=1;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(bitAnd(x , y) != test_bitAnd(x,y))
{
result = 1;
printf("[Wrong! with %d != %d]\n",bitAnd(x , y), test_bitAnd(x,y));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO2
result=0;
Case=2;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(bitNor(x , y) != test_bitNor(x,y))
{
result = 1;
printf("[Wrong! with %d != %d]\n",bitAnd(x , y), test_bitAnd(x,y));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO3
result=0;
Case=3;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(copyLSB(x) != test_copyLSB(x))
{
result = 1;
printf("[Wrong! with %d != %d]\n",copyLSB(x), test_copyLSB(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO4
result=0;
Case=4;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(evenBits() != test_evenBits())
{
result = 1;
printf("[Wrong! with %d != %d]\n",evenBits(), test_evenBits());
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO5
result=0;
Case=5;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()%31;
if(logicalShift(x , y) != test_logicalShift(x,y))
{
result = 1;
printf("[Wrong! with %d != %d]\n",logicalShift(x , y), test_logicalShift(x,y));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO6
result=0;
Case=6;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(bang(x) != test_bang(x))
{
result = 1;
printf("[Wrong! with %d != %d]\n",bang(x), test_bang(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO7
result=0;
Case=7;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(leastBitPos(x) != test_leastBitPos(x))
{
result = 1;
printf("[Wrong! with %d got %d != %d]\n",x,leastBitPos(x ), test_leastBitPos(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO8
result=0;
Case=8;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if( tmax() != test_tmax())
{
result = 1;
printf("[Wrong! with %d != %d]\n",tmax(), test_tmax());
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO9
result=0;
Case=9;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(negate(x ) != test_negate(x))
{
result = 1;
printf("[Wrong! with %d != %d]\n",negate(x ), test_negate(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO10
result=0;
Case=10;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(isPositive(x) != test_isPositive(x))
{
result = 1;
printf("[Wrong! with %d got %d != %d]\n",x,isPositive(x), test_isPositive(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO11
result=0;
Case=11;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
if(isNonNegative(x ) != test_isNonNegative(x))
{
result = 1;
printf("[Wrong! with %d != %d]\n",isNonNegative(x), test_isNonNegative(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO12
result=0;
Case=12;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
int z = rand()-RAND_MAX/2;
if(sum3(x , y,z) != test_sum3(x,y,z))
{
result = 1;
printf("[Wrong! with %d != %d]\n",sum3(x , y,z), test_sum3(x,y,z));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO13
result=0;
Case=13;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(addOK(x , y) != test_addOK(x,y))
{
result = 1;
printf("[Wrong! with %d != %d]\n",addOK(x , y), test_addOK(x,y));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO14
result=0;
Case=14;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(abs(x ) != test_abs(x))
{
result = 1;
printf("[Wrong! with %d != %d]\n",abs(x ), test_abs(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
//function: NO15
result=0;
Case=15;
for(i = 0; i < 1000000; i++)
{
int x = rand()-RAND_MAX/2;
int y = rand()-RAND_MAX/2;
if(isNonZero(x ) != test_isNonZero(x))
{
result = 1;
printf("[Wrong! with %d got %d != %d]\n",x,isNonZero(x ), test_isNonZero(x));
break;
}
}
if(result != 0)
printf("NO.%d. Result is wrong with test case:%d\n",Case,result);
else
printf("NO.%d. All Passed!\n",Case);
return 0;
}