Download it from csAPP Lab’s official website
The directory structure after the download should look like this
We need to modify the bits file. And make then looks at the examples that btest passes to determine the score
First, implement bitXor
Use ~ and & to implement ^
x ^ y = (x | y) & (~x | ~y)
a | b = ~(~a & ~b)
So x ^ y = ~(~ x&y) &~ (x&y)
int bitXor(int x, int y) {
return ~(~x & ~y) & ~(x & y);
}
Copy the code
Problem number two, tMIN
Returns the minimum binary complement integer qualified using “! ~ & ^ | + < < > >”
According to the nature of the complement 10,000… (1 followed by 31 zeros) is this number
So return 1 << 31
int tmin(void) {
return 1 << 31;
}
Copy the code
Problem number three, implement isTmax
If x is tmax(011111…) Returns 1, others return 0
Tmax (~(tmax + 1)) = 000000... But 0xffffFFFF also satisfies this, so you need to exclude 0xFFFFFFFF so return! ((x ^ (~(x + 1))) | (! (~x)) only tmax and 0xFFFFFFFF are 0 for the first part and only tmax is 0 for the second partCopy the codeint isTmax(int x) {
/* if x is tmax then tmax == ~(tmax + 1) */
/* but x ! = 0xffffffff */
/* if x == tmax , x ^ (~(x + 1)) == 0x00000... and ! (~x) == false, return true(1) */
/* if x == 0xffffffff, x ^(~(x + 1)) == 0x00000... but ! (~x) == true , return false(0)*/
/* if x ! = tmax and x ! = 0xffffffff, x ^ (~(x + 1)) ! = 0, return false(0)*/
return! ((x ^ (~(x +1))) | (! (~x))); }Copy the code
Fourth problem, implement addOddBits
Returns 1 if all the even digits of one number are 1, and 0 for the others
Is to determine whether a number is equal to 0xAAAAAAAA. The return! (x ^ 0xAAAAAAAA) However, there are restrictions on using more than 8 bits directlyCopy the codeint allOddBits(int x) {
/* if x == 0xAAAAAAAA return 1 */
/* if x ^ 0xAAAAAAAA == 0 return 1 else return 1 */
/* so return ! (x ^ 0xAAAAAAAA) */
int mask = 0xAA | 0xAA << 8;
mask = mask << 16 | mask;
x = x & mask;
return! (mask ^ x); }Copy the code
5. Implement negate
Given x, return -x
Return ~x + 1 according to the properties of the complementCopy the codeint negate(int x) {
/* return ~x + 1 */
return ~x + 1;
}
Copy the code
Number six, implement isAsciiDigit
If 0x30 <= x <= 0x39 returns 1, others return 0
Let’s look at the 4-digit complement minus 8 to 7, and pick 2 minus 4
We take a number 0011(the sign bit is 0, the inverse of the integer part is 4), add a number larger than 4 and the overflow will occur and the sign bit will be 1. Another number 1101(the inverse of 2), plus a number less than 2 plus 1 will not overflow, and the sign bit will be 1
So we have the following code to derive it
int isAsciiDigit(int x) {
/* if upperBound add a number which biger 0x39 upperBound change negate */
/* if lowerBound add a number which lower 0x30 lowerBound change negate */
int sign = 0x1 << 31;
int upperBound = ~(sign | 0x39);
int lowerBound = ~0x30;
upperBound = sign & (upperBound + x) >> 31;
lowerBound = sign & (lowerBound + 1 + x) >> 31;
return! (upperBound | lowerBound); }Copy the code
Problem seven, realizing coditional
A given x, y, z. Achieve x? y: z;
So let’s convert x to either 0 or 1. x = !! x; If x is 0 then x =!! After x, x is 0. If x is not 0, x =!! After x, x becomes 1 and then converts x to ~x + 1. If the beginning of 0 x, x is 0 x00000000, otherwise the x is 0 XFFFFFFFF finally return (x & y) | (~ x and z) is requested
int conditional(int x, int y, int z) { x = !! x;// if x == 0, then x = 0, else x = 1
x = ~x + 1; // if x == 0, then x = 0x00000000, else x = 0xffffffff
return (x & y) | (~x & z); // if x == 0, then return z, else return y
}
Copy the code
Problem 8. Implement isLessOrEqual
Return 1 if x <= y, 0 if x <= y then y – x >= 0. But if x and y are oppositely positive and negative, it might spill over and there are two ways to do it. Y – x >= 0 or y >= 0 &&x < 0 returns 1 and everything else returns 0 and the code here is to determine if the sign of y – x is the opposite of x and y is negative and x is negative
int isLessOrEqual(int x, int y) {
int negx = ~x + 1; // -x
int addx = negx + y;// y - x
int sign = addx >> 31 & 1; // (y - x)' sign, if x less or equal y, then y - x >= 0
int leftBit = 1 << 31; // 0b1000000...
int signx = x & leftBit; // x' sign
int signy = y & leftBit; // y' sign
int bitXor = signx ^ signy; // if x and y both positive or negate then bitXor is 0 else bitXor is not zero
bitXor = (bitXor >> 31) & 1; // if x and y both positive or negate then bitXor is 0 else bitXor is 1
return((! bitXor) & (! sign)) | (bitXor & (signx >>31));
}
Copy the code
Problem 9, implement logicalNeg
If 0, return 1; If it is other, returns 0 0 has a characteristic 0 is the complement of its own, so | 0 (0 ~ + 1) > > 31 to 0. Several other will have 0 XFFFFFFFF so return ((x | (~ x + 1)) > > 31) + 1
int logicalNeg(int x) {
/* if x equal 0, then (x | (~x + 1)) >> 31 if 0x00000000, return 1*/
/* else return 0xffffffff + 1 equal 0 */
return ((x | (~x + 1)) > >31) + 1;
}
Copy the code
Implement howManyBits
Returns a number representing how many bits its binary complement requires. For example, -5 returns 4 and 12 returns 5, so we just need the xor adjacent number x^=(x<<1) to find the highest digit of 1.
int howManyBits(int x) {
int n = 0;
x ^= (x<<1); n += ((!! (x & ((~0) << (n + 16)))) < <4); n += ((!! (x & ((~0) << (n + 8)))) < <3); n += ((!! (x & ((~0) << (n + 4)))) < <2); n += ((!! (x & ((~0) << (n + 2)))) < <1); n += (!! (x & ((~0) << (n + 1))));
return n + 1;
}
Copy the code
Implement floatScale2
Consider the special case of NaN and INF, i.e. Exp ==255, if((uf&0x7fffffff) >= 0x7F800000), and return the argument. Consider the +0/-0 case, if(! (uf& 0x7FFffFFf)), returns 0.
If the result is still a normalized decimal 0.5, only the exponent -1 is required, leaving the rest unchanged. (uf & 0 x807fffff) | (– exp_) < < 23. Normalize the decimal 0.5, and the possible result becomes nonnormalized. That is, exp==0 or exp==1. In this case, only the decimal part is dealt with, because the exponential part of the nonnormalized decimal is 0, and a shift to the right means *0.5.
unsigned floatScale2(unsigned uf) {
int exp = (uf & 0x7f800000) > >23;
int sign = uf & (1 << 31);
if(exp= =0)
return uf << 1 | sign;
if(exp= =255)
return uf;
exp+ +;if(exp= =255)
return 0x7f800000 | sign;
return (exp << 23) | (uf & 0x807fffff);
}
Copy the code
Implement floatFloat2Int
Floating-point number can be divided into three parts, first part symbol s_ = uf > > 31, exp_ index size = ((uf & 0 x7f800000) > > 23) – 127, obtain the decimal part, and floating points to the default of 1, frac_ = (uf & 0 x007fffff) | 0 x00800000.
If all zeros are used in special cases, 0 is returned. If the index is greater than 31, 0x80000000 cannot be returned as an integer. If the exponent is less than 0, the number 0<x<1 returns 0.
If the exponent is greater than 23, move the decimal fraction to the left frac_ <<= (exp_ -23), where exp_ represents the exponent.
If the exponent part is less than 23, move the decimal part to the right FRAC_ >>= (23-exp_), exp_ represents the exponent size.
Considering the final sign, there is no overflow from a positive to a negative number. If frac_ is positive, adjust the positive and negative outputs according to s_.
If FRAC_ is negative, the only correct case is 0x80000000.
int floatFloat2Int(unsigned uf) {
int s_ = uf >> 31;
int exp_ = ((uf & 0x7f800000) > >23) - 127;
int frac_ = (uf & 0x007fffff) | 0x00800000;
if(! (uf &0x7fffffff))
return 0;
if(exp_ > 31)
return 0x80000000;
if(exp_ < 0)
return 0;
if(exp_ > 23)
frac_ <<= (exp_ - 23);
else
frac_ >>= (23-exp_);
if(! ((frac_>>31)^s_))
return frac_;
else if(frac_>>31)
return 0x80000000;
else
return ~frac_+1;
}
Copy the code
Implement floatPower2
Compute a floating point number 2.0^x. Returns 0 if the result is too small, +INF if the result is too large
unsigned floatPower2(int x) {
int INF = 0xff<<23;
int exp = x + 127;
if(exp< =0)
return 0;
if(exp> =255)
return INF;
return exp << 23;
}
Copy the code
Finally, run the btest file after making
