CS:APP Data Lab
The purpose of this lab is to become more familiar with bit-level representations of integers andfloating point numbers. 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.———— Harry Bovik
bitXor
- bitXor - x^y using only ~ and &
- Example: bitXor(4, 5) = 1
- Legal ops: ~ &
- Max ops: 14
- Rating: 1
1
2
3
4
5
| int bitXor(int x, int y)
{
// x^y=(x&~y)|(~x&y)=~(~x&~y)&~(x&y)
return ~(~(x & ~y) & ~(~x & y));
}
|
tmin
- tmin - return minimum two’s complement integer
-
- Max ops: 4
- Rating: 1
1
2
3
4
| int tmin(void)
{
return 1 << 31;
}
|
isTmax
- isTmax - returns 1 if x is the maximum, two’s complement number, and 0 otherwise
-
- Max ops: 10
- Rating: 1
1
2
3
4
| int isTmax(int x)
{
return !(~(x + 1) ^ x) & !!(x + 1);
}
|
allOddBits
- allOddBits - return 1 if all odd-numbered bits in word set to 1
- where bits are numbered from 0 (least significant) to 31 (most significant)
- Examples: allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
-
- Max ops: 12
- Rating: 2
1
2
3
4
5
6
| int allOddBits(int x)
{
int m = (0xAA << 8) | 0xAA;
m = (m << 16) | m;
return !((x & m) ^ m);
}
|
negate
- negate - return -x
- Example: negate(1) = -1.
-
- Max ops: 5
- Rating: 2
1
2
3
4
| int negate(int x)
{
return ~x + 1;
}
|
isAsciiDigit
- isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters ‘0’ to ‘9’)
- Example: isAsciiDigit(0x35) = 1.
- isAsciiDigit(0x3a) = 0.
- isAsciiDigit(0x05) = 0.
-
- Max ops: 15
- Rating: 3
1
2
3
4
5
6
| int isAsciiDigit(int x)
{
int a = x + (~0x30 + 1);
int b = 0x39 + (~x + 1);
return !((a >> 31) | (b >> 31));
}
|
conditional
- conditional - same as x ? y : z
- Example: conditional(2,4,5) = 4
-
- Max ops: 16
- Rating: 3
1
2
3
4
| int conditional(int x, int y, int z)
{
return ((~(!!x) + 1) & y) | ((~(~(!!x) + 1)) & z);
}
|
isLessOrEqual
- isLessOrEqual - if x <= y then return 1, else return 0
- Example: isLessOrEqual(4,5) = 1.
-
- Max ops: 24
- Rating: 3
1
2
3
4
5
6
7
8
| int isLessOrEqual(int x, int y)
{
int a = (x >> 31) & 1, b = (y >> 31) & 1;
int f = a ^ b;
int d = y + ~x + 1;
int ds = (d >> 31) & 1;
return (f & a) | (!f & !ds);
}
|
logicalNeg
- logicalNeg - implement the ! operator, using all of the legal operators except !
- Examples: logicalNeg(3) = 0, logicalNeg(0) = 1, logicalNeg(-5) = 0
-
- Max ops: 12
- Rating: 4
1
2
3
4
| int logicalNeg(int x)
{
return (((~x + 1) | x) >> 31) + 1;
}
|
howManyBits
- howManyBits - return the minimum number of bits required to represent x in two’s complement
- Examples: howManyBits(12) = 5
- howManyBits(298) = 10
- howManyBits(-5) = 4
- howManyBits(0) = 1
- howManyBits(-1) = 1
- howManyBits(0x80000000) = 32
-
- Max ops: 90
- Rating: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int howManyBits(int x)
{
int sign = x >> 31, bit16, bit8, bit4, bit2, bit1;
x = (sign & ~x) | (~sign & x);
bit16 = (!!(x >> 16)) << 4;
x >>= bit16;
bit8 = (!!(x >> 8)) << 3;
x >>= bit8;
bit4 = (!!(x >> 4)) << 2;
x >>= bit4;
bit2 = (!!(x >> 2)) << 1;
x >>= bit2;
bit1 = (!!(x >> 1));
x >>= bit1;
return bit16 + bit2 + bit4 + bit8 + bit1 + x + 1;
}
|
floatScale2
- floatScale2 - Return bit-level equivalent of expression 2*f for floating point argument f.
- Both the argument and result are passed as unsigned int’s, but they are to be interpreted as the bit-level representation of single-precision floating point values.
- When argument is NaN, return argument
-
| Legal ops: Any integer/unsigned operations incl. |
|
, &&. also if, while |
- Max ops: 30
- Rating: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| unsigned floatScale2(unsigned uf)
{
unsigned sign = (uf >> 31) & 1, exp = (uf >> 23) & 0xff, frac = uf & 0x7fffff;
if (exp == 0xff)
return uf;
if (exp == 0)
{
if (frac & 0x800000)
{
exp = 1;
}
frac <<= 1;
return (exp << 23) | (sign << 31) | frac;
}
exp++;
if (exp == 0xff)
{
return (sign << 31) | (0xff << 23);
}
return (sign << 31) | (exp << 23) | frac;
}
|
floatFloat2Int
- floatFloat2Int - Return bit-level equivalent of expression (int) f for floating point argument f.
- Argument is passed as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point value.
- Anything out of range (including NaN and infinity) should return 0x80000000u.
-
| Legal ops: Any integer/unsigned operations incl. |
|
, &&. also if, while |
- Max ops: 30
- Rating: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int floatFloat2Int(unsigned uf)
{
int sign = uf >> 31, exp = ((uf >> 23) & 0xff) - 127, frac = (uf & 0x7fffff) | 0x800000;
if (exp >= 31)
return 0x80000000u;
if (exp < 0)
return 0;
if (exp < 23)
{
frac >>= (23 - exp);
}
else
{
frac <<= (exp - 23);
}
if (sign)
{
frac = -frac;
}
return frac;
}
|
floatPower2
- floatPower2 - Return bit-level equivalent of the expression 2.0^x (2.0 raised to the power x) for any 32-bit integer x.
- The unsigned value that is returned should have the identical bit representation as the single-precision floating-point number 2.0^x.
- If the result is too small to be represented as a denorm, return 0. If too large, return +INF.
-
| Legal ops: Any integer/unsigned operations incl. |
|
, &&. Also if, while |
- Max ops: 30
- Rating: 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| unsigned floatPower2(int x)
{
if (x < -148)
{
return 0;
}
if (x < -126)
{
unsigned f = x + 148;
unsigned fra = 1 << f;
return fra;
}
if (x <= 127)
{
int k = x + 127;
return k << 23;
}
return 0x7f800000;
}
|
