首先声明datalab本人未完成,有4道题目没有做出来。本文博客记录下自己的解析,以便以后回忆。如果能帮助到你就更好了,如果觉得本文没啥技术含量,也望多多包涵。
/*
* 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);
}
/*
* 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) {
int offsetValue = 0xff;
int offsetIndex = n << 3;
int value = (x & (offsetValue << offsetIndex)) >> offsetIndex;
return value & offsetValue;
}
/*
* logicalShift - shift x to the right by n, using a logical shift
* Can assume that 0 <= n <= 31
* Examples: logicalShift(0x87654321,4) = 0x08765432
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 20
* Rating: 3
*/
int logicalShift(int x, int n) {
int offset = 0x1 << 31;
int offsetValue = ~(offset >> n << 1);
return (x >> n) & offsetValue;
}
/*
* bitCount - returns count of number of 1's in word
* Examples: bitCount(5) = 2, bitCount(7) = 3
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 40
* Rating: 4
*/
int bitCount(int x) {
return 2;
}
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
return 2;
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return (0x1 << 31);
}
/*
* fitsBits - return 1 if x can be represented as an
* n-bit, two's complement integer.
* 1 <= n <= 32
* Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int fitsBits(int x, int n) {
int offsetValue = 0x1 << n;
int addValue = (offsetValue >> 1) & (~offsetValue);//2^(n-1)
int value1 = x + addValue;//x - {-[2^(n-1)]}
int value2 = addValue + (~x);//[2^(n-1)-1] - x
int maxValue = 0x1 << 31;
return (n >> 5) | ((!(value1 & maxValue)) & (!(value2 & maxValue)));
}
/*
* divpwr2 - Compute x/(2^n), for 0 <= n <= 30
* Round toward zero
* Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 2
*/
int divpwr2(int x, int n) {
int maxValue = 0x1 << 31;
int offsetValue = ~(0x1 << 31 >> (32 + ~n));
int andValue = offsetValue & x;
return (x >> n) + ((!!(x & maxValue)) & (!!(andValue)));
}
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
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) {
return (!(x >> 31)) ^ (!x);
}
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 24
* Rating: 3
*/
int isLessOrEqual(int x, int y) {
int offsetValue = 0x1;
int offsetIndex = 31;
int offsetSign = offsetValue << offsetIndex;
int signX = !(x & offsetSign);
int signY = !(y & offsetSign);
int value1 = ((!signX) & signY )^ 0x0;
int value2 = (signX & (!signY)) ^ 0x1;
int value3 = (!((y + ~x + 1) & offsetSign)) ^ 0x0;
return value1 | (value2 & value3);
}
/*
* ilog2