/*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd(int x, int y) {
// ~(x && y) == ~x | ~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) {
// n >> 3 == n * 8
return x >> (n << 3) & 0xff;
}
/*
* 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) {
// mask inserted 1s from arithmetic shift
// return (x >> n) & (0xffffffff >> n);
// 32+~n == 31-n
int mask = ((1 << (32 + ~n)) + ~0) | (1 << (32 + ~n));
return (x >> n) & mask;
}
/*
* 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) {
// https://stackoverflow.com/questions/3815165/how-to-implement-bitcount-using-only-bitwise-operators
int mask_3333 = 0x33, mask_5555 = 0x55, mask_0F0F = 0x0f, mask_00FF = 0xff,
mask_FFFF = 0xff, c;
mask_3333 |= mask_3333 << 8;
mask_3333 |= mask_3333 << 16;
mask_5555 |= mask_5555 << 8;
mask_5555 |= mask_5555 << 16;
mask_0F0F |= mask_0F0F << 8;
mask_0F0F |= mask_0F0F << 16;
mask_00FF |= mask_00FF << 16;
mask_FFFF |= mask_FFFF << 8;
c = (x & mask_5555) + ((x >> 1) & mask_5555);
c = (c & mask_3333) + ((c >> 2) & mask_3333);
c = (c & mask_0F0F) + ((c >> 4) & mask_0F0F);
c = (c & mask_00FF) + ((c >> 8) & mask_00FF);
c = (c & mask_FFFF) + ((c >> 16) & mask_FFFF);
return c;
}
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang(int x) {
// the goal is to | every bit in x, the result is at the 0th bit
x |= (x >> 16);
x |= (x >> 8);
x |= (x >> 4);
x |= (x >> 2);
x |= (x >> 1);
return ~x & 1;
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
// 0x10000000
return 1 << 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) {
// only under two cases return 1: (n-1)th bit to 31st bit is all 0 or 1
// solution 1
// c = 32 - n;
int c = 33 + ~n;
int r = x << c >> c;
// r should be identical to x
return !(x ^ r);
// solution 2
// x >> n-1
// x >>= n + ~0;
// // now x should be either -1 or 0
// return !(x + 1) | !x;
}
/*
* 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) {
// if x < 0, only when the 0th to (n-1)th bit of x are all 0s will x>>n == x
// https://stackoverflow.com/questions/5061093/dividing-by-power-of-2-using-bit-shifting
return (x + ((x >> 31) & ((1 << n) + ~0))) >> n;
}
/*
* 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) {
// !(x>>31) is to determine whether x >= 0, !!x to determine whether x==0
return !!x & !(x >> 31);
}
/*
* 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) {
// y - x
int tmp = y + ~x + 1;
// avoid overflow. if y > 0 && x < 0, return 1. if y < 0 && x > 0, return 0.
x >>= 31;
y >>= 31;
// return !(!!y & !x) & ((!y & !!x) | !(tmp >> 31)); // equivalent to
return (!y | !!x) & ((!y & !!x) | !(tmp >> 31));
}
/*
* ilog2 - return floor(log base 2 of x), where x > 0
* Example: ilog2(16) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/
int ilog2(int x) {
// the answer could be written as 16a+8b+4c+2d+e, abcde are computed successively
int ans = 0;
ans = (!!(x >> (16))) << 4;
ans += ((!!(x >> (8 + ans))) << 3);
ans += ((!!(x >> (4 + ans))) << 2);
ans += ((!!(x >> (2 + ans))) << 1);
ans += ((!!(x >> (1 + ans))) << 0);
return ans;
}
/*
* float_neg - Return bit-level equivalent of expression -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 representations of
* single-precision floating point values.
* When argument is NaN, return argument.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 10
* Rating: 2
*/
unsigned float_neg(unsigned uf) {
// determine whether it is NaN (exp == 0xff, frac > 0)
if (!((uf + 0x00800000) & 0x7f800000) && (uf << 9)) return uf;
return uf ^ 0x80000000;
}
/*
* float_i2f - Return bit-level equivalent of expression (float) x
* Result is returned as unsigned int, but
* it is to be interpreted as the bit-level representation of a
* single-precision floating point values.
* Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
* Max ops: 30
* Rating: 4
*/
unsigned float_i2f(int x) {
// sign | exp | frac: 1-bit, 8-bit, 23-bit
unsigned sign, exp;
// omit sign. abs is used to compute the frac. tmps are for saving ops
unsigned abs = x, abs_copy, tmp, tmp2, tmp3, tmp4;
// the place of the highest 1
unsigned n = -1;
// denormalized representation for 0
if (!x) return 0;
// special case
if (x == 0x80000000) return 0xcf000000;
sign = x & 0x80000000;
if (sign) abs = -x;
abs_copy = abs;
// suppose x = 10110101, then it could represented as 1.0110101 * 2^7
// so the bits after x's highest 1 are in frac, and the place of the highest
// 1 is e find the highest 1
while (abs_copy) {
abs_copy >>= 1;
++n;
}
// the frac part. when n == 0, 0xffffffff>>(32-n) == 0xffffffff.
if (n)
abs &= 0xffffffff >> (32 - n);
else
abs = 0;
// 0th to (n-1)-th bits are in frac
// if the length of frac > 23, right shift; else left shift
if (n > 23) {
// need to consider rounding problems (round-to-even)
// if there are 1s in the low bits (n-23) to be rounded
tmp = abs & (0xffffffff >> (55 - n)); // the rounded part
tmp4 = n - 23; // just for saving ops
tmp2 = 1 << tmp4;
tmp3 = tmp2 >> 1;
// upper round
if (tmp > tmp3)
abs += tmp2;
else if (tmp == tmp3) {
// at middle
// if the lowest keeped bit is 1, it should be rounded to even
if (abs & tmp2) abs += tmp2;
}
abs >>= tmp4;
} else {
abs <<= (23 - n);
}
// if after rounding, the frac part has a 1 at 23th bit, this 1 would be
// treated as a carry and add 1 to the exp
if (abs & 0x800000) {
++n;
abs &= 0x7fffff;
}
// exp == e + bias
exp = (n + 127) << 23;
return sign | exp | abs;
}
/*
* float_twice - 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
*/
unsigned float_twice(unsigned uf) {
unsigned sign = uf & 0x80000000, exp = uf & 0x7f800000, frac = uf & 0x7fffff;
// determine whether it is NaN or INF (exp == 0xff)
if (!((uf + 0x00800000) & 0x7f800000)) return uf;
else if (!exp) {
// denormalized. e == 1-bias, f == frac
return sign | (frac << 1);
// if frac<<1 is larger than 0x7fffff, a carry bit would be added to the exp part,
// resulting in a normalized float with a "free" 1 in frac
} else {
// normalized
// if exp < 0xfe, just need to add 1 to exp. else 2*uf is INF
if (exp == 0x7f000000) return sign | 0x7f800000;
return uf + 0x00800000;
}
}
Home