Copy /*
* bitAnd - x&y using only ~ and |
* Example: bitAnd(6, 5) = 4
* Legal ops: ~ |
* Max ops: 8
* Rating: 1
*/
int bitAnd ( int x , int y) {
/* To achieve "x & y" expression */
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) {
/*
* All number is 0 | 1 in nature
* so if you wanna mutiplie, consider shift
* First, deal parameter 'n', make it * 8
* then shift 'x', last clear
*/
return (x >> (n << 3 )) & 0x FF ;
}
/*
* 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) {
/* Deal negative number high bit 1 */
int recover = ( 1 << 31 ) >> n << 1 ;
return ((x >> n) & ~ recover);
}
/*
* 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) {
int count;
int tpMask1 = 0x 55 | ( 0x 55 << 8 );
int mask1 = tpMask1 | (tpMask1 << 16 ); //01010101
int tpMask2 = 0x 33 | ( 0x 33 << 8 );
int mask2 = tpMask2 | (tpMask2 << 16 ); //00110011
int tpMask3 = 0x 0f | ( 0x 0f << 8 );
int mask3 = tpMask3 | (tpMask3 << 16 ); //00001111
int mask4 = 0x ff | ( 0x ff << 16 ); //00000000 11111111
int mask5 = 0x ff | ( 0x ff << 8 ); //00000000 00000000 11111111 11111111
count = (x & mask1) + ((x >> 1 ) & mask1);
count = (count & mask2) + ((count >> 2 ) & mask2); //每4位一组,先计算低位的两位,右移2位后再计算高位两位
count = (count + (count >> 4 )) & mask3; //每8位一组
count = (count + (count >> 8 )) & mask4; //每16位一组
count = (count + (count >> 16 )) & mask5; //总共32位为一组,将前16位的结果与后16位的结果相加即得最终答案
return count;
}
/*
* bang - Compute !x without using !
* Examples: bang(3) = 0, bang(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int bang ( int x) {
/* Self | self own complement get full 1 and then shift sign bit */
int complement = ~ x + 1 ;
return ((x | complement) >> 31 ) + 1 ;
}
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin ( void ) {
/* According to the two's complement computation rule */
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) {
/*
* Judge how many bits we need to represent this num
* Which means using shift operation doesn't change value
* First expand to higher bit and move back
* Meanwhile, ~n + 1 == -n (two's complement)
*/
int shift = 32 + ( ~ n + 1 );
return ! (x ^ ((x << shift) >> shift));
}
/*
* 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) {
/* Check and then shift, negative low n bit add themself */
int mask = ~ (( 1 << 31 ) >> 31 << n); /* 00001111 */
int b = (x >> 31 ) & mask; /* self += self must be even */
return (x + b) >> 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) {
/* Judge from highest bit & 0? */
int sign = x >> 31 ;
int is_not_zero = !! x;
return (is_not_zero & ! sign);
}
/*
* 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) {
/* Use substraction, and then observe signed bit */
int difference = y + ( ~ x) + 1 ;
int x_sign = x >> 31 ;
int y_sign = y >> 31 ;
int same = ! (x_sign ^ y_sign);
int diff_sign = difference >> 31 ;
return (( ! same) & x_sign) | (same & ! (diff_sign));
}
/*
* 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) {
/* Dichotomy to find the highest one */
int count = 0 ;
count = !! (x >> 16 ) << 4 ;
count += !! (x >> (count + 8 )) << 3 ;
count += !! (x >> (count + 4 )) << 2 ;
count += !! (x >> (count + 2 )) << 1 ;
count += !! (x >> (count + 1 ));
return count;
}
/*
* 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) {
/* Whether a NaN */
if ((( 0x FF000000 & (uf << 1 )) == 0x FF000000 ) /* exp == 11111111 */
&& (uf << 1 ) != 0x FF000000 ) /* frac != 0 */
return uf;
else return uf ^ 0x 80000000 ;
}
/*
* 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) {
/* int -> float, sign + exp + frac */
/* special cases */
if (x == 0x 80000000 ) return 0x cf000000 ;
if (x == 0 ) return 0 ;
/* sign */
unsigned sign = (x >> 31 ) << 31 ;
/* exp */
int abs_x = x;
/* get abs x */
if (abs_x < 0 ) abs_x = - x;
int tmp = abs_x;
int highest_bit = 0 ;
while (tmp) {
highest_bit ++ ;
tmp >>= 1 ;
}
int weight = highest_bit - 1 ;
unsigned exp = ( 127 + weight) << 23 ;
/* frac */
unsigned frac , frac_cut;
if (weight > 23 ) {
frac = (abs_x >> (weight - 23 )) & 0x 7fffff ;
frac_cut = (abs_x << ( 31 - weight)) & 0x ff ;
/* carry */
if ((frac_cut > 0x 80 ) || (frac_cut == 0x 80 && (frac & 1 ))) {
frac ++ ;
}
} else frac = (abs_x << ( 23 - weight)) & 0x 7fffff ;
return sign + exp + frac;
}
/*
* 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) {
/* sign + exp + frac */
/* sign */
unsigned sign = (uf >> 31 ) << 31 ;
/* exp & frac */
unsigned exp = uf & 0x 7f800000 ;
unsigned frac = uf & 0x 7fffff ;
/* Deal with different situations */
if (exp == 0x 7f800000 ) return uf;
else {
if (exp == 0 ) frac <<= 1 ;
else exp += 0x 800000 ;
}
return sign + exp + frac;
}