bitXor
We only can use the operations ~ and & realize the xor operation function.
We have to know what’s function of the xor is. When the number is not the same, return 1 or 0.
If x is equal y, (x&~y) = ~(x&y). According to the formula, we can get the answer to this challenge.
//1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
return ~(~x&~y)&~(x&y);
}
/*
* if x = y
* x & ~x = 0
*
*/tmin
What’s the minimum number in integer? How to represent the minimum number in binary?
As we know integer is 32bit: (the first is sign bit)
so the minimum number is : 1000 0000 0000 0000 0000 0000 0000 0000
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 0x1<<31;
}
//2isTmax
When the variable pass to the function, we should decide whether it is the max in integer. If it is the max number return 1 or 0.
How to figure it?
Tmax in integer: 0111 1111 1111 1111 1111 1111 1111 1111
The complement is: 1000 0000 0000 0000 0000 0000 0000 0000
-1: 1111 1111 1111 1111 1111 1111 1111 1111-1: 0000 0000 0000 0000 0000 0000 0000 0000-1) -> 1 that’s what we want to return the value when the variable is Tmax :-)
!(
But if the x is negative 1, we can also get the same value, so we have to exclude the particular variable.
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
int isTmax(int x) {
int i = x+1; // negative 1
x = x + i;
x=~x;
i=!i; // if the x is -1, i is zero -> !i is 1, x is zero
x=x+i; // if x+i = 1 -> !x = 0
return !x;
//
// TMAX 0111 1111 1111 1111 1111
// TMIN 1000 0000 0000 0000 0000
// -1 1111 1111 1111 1111 1111
// TMAX = ~TMIN
// ~-1 = 0
//
// TMAX return 1, other return 0;
}allOddbits
I think it is the most accessible stuff of all challenges.
0xAA: 1010 1010
0xAA << 8 : 1010 1010 0000 0000
mask -> 0xAA << 8 + 0xAA: 1010 1010 1010 1010
mask -> mask + mask << 16: 1010 1010 1010 1010 1010 1010 1010 1010
That’s how we get the all0ddBits number in shift way.
If x is all odd-numbered bits in the word set to 1, x&mask value is equal to the mask, and xor the mask to decide whether it is the same value.
/*
* 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
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 12
* Rating: 2
*/
int allOddBits(int x) {
int mask = 0xAA + (0xAA<<8);
mask = mask + (mask << 16);
return !((mask&x)^mask);
}negate
Too easy to explain….
x+(~x)=-1
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x+1;
}isAsciiDigit
We can set the bound to ensure the x whether is between 0x30 and 0x39.
If the x is bigger than 0x39, upperBound plus x will change the sign bit, which lets’s know x is exceed.
Conversely, if the x is smaller than 0x30, lowerBound plus x will also change the sign bit.
//3
/*
* isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
* Example: isAsciiDigit(0x35) = 1.
* isAsciiDigit(0x3a) = 0.
* isAsciiDigit(0x05) = 0.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 15
* Rating: 3
*/
int isAsciiDigit(int x) {
int sign = 0x1 << 31; // get the sign bit
int upperBound = ~(sign | 0x39);
int lowerBound = ~0x30+1;
upperBound = sign&(upperBound+x)>>31;
lowerBound = sign&(lowerBound+x)>>31;
return !(upperBound|lowerBound);
}conditional
Let x only two values, 0 or 1. That’s why we set the flag variable.
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
int flag = !!x;
flag = ~flag+1; // ---> if x is 1 --> -1; if x is zero ----> 0
// -1 & any values is itself.
return (flag&y)|(~flag&z);
}/*
* 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 negx = ~x+1;
int sign = (negx+y)>>31&1; // x,y > 0
// x,y at most one is greater than 0
// check x && y sign bit
int xsign = x>>31&1;
int ysign = y>>31&1;
// whether x and y is same sign
int bitXor = xsign^ysign;
return( (!bitXor)&(!sign) | bitXor&xsign);
}/*
* logicalNeg - implement the ! operator, using all of
* the legal operators except !
* Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
* Legal ops: ~ & ^ | + << >>
* Max ops: 12
* Rating: 4
*/
int logicalNeg(int x) {
return((x|(~x+1))>>31)+1;
// (x|~x+1)>>31 == -1 if x!=0
// (x|~x+1)>>31 == 0 if x =0
}
/* 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
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 90
* Rating: 4
*/howManyBits
To be honestly, it’s must be the most interesting challenge in all stuffs.
We must know that the binary digits of a number are the same as its complement number. So if the number is negative, we can get its complement number.
And we can use the dichotomy to check the bits.
example:
0000 1000 0000 1100 0000 0000 1111 0000
b16 = !!(x>>16)<<4 -> 16
x = x>>b16 —–> 0000 1000 0000 1100
We should know the index of the first 1 bit. (postive number)
We can add all variables and sign bit to get the sum of bits.
int howManyBits(int x) {
int sign = x>>31;
int b0,b1,b2,b4,b8,b16;
// if x is negative -> make it positive
x = (sign&~x)|(~sign&x);
b16 = !!(x>>16)<<4;
x = x>>b16;
b8 = !!(x>>8)<<3;
x = x>>b8;
b4 = !!(x>>4)<<2;
x = x>>b4;
b2 = !!(x>>2)<<1;
x = x>>b2;
b1 = !!(x>>1);
x = x>>b1;
b0 = x;
return b16+b8+b4+b2+b1+b0+1;
}floatScale2
- We have to get 3 parts in float number, sign, expr and frac.
//float
/*
* 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
*/
unsigned floatScale2(unsigned uf) {
// float = (sign << 31)| (expr << 23) | frac
int sign,expr,frac;
sign = uf>>31 & 1;
expr = uf>>23 & 0xFF;
frac = uf & (0x7FFFFF);
// 0
if(expr == 0 && frac ==0){
return uf;
}
// inifity or NAN
if(expr == 255){
return uf;
}
// denormalize
if(expr == 0 && frac != 0){
frac <<= 1;
return (sign<<31)|(frac);
}
// normalize
if(expr > 0 && expr < 255){
expr++;
return (sign<<31)|(expr<<23)|(frac);
}
}Float2Int
/*
* 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
*/
int floatFloat2Int(unsigned uf) {
int sign,expr,frac;
sign = uf>>31 & 1;
expr = uf>>23 & 0xff;
frac = uf & 0x7fffff;
// 0
if(expr == 0 && frac == 0){
return 0;
}
// inifity or NAN
if(expr == 255){
return 1<<31;
}
// denormalize
// 0.xxxxxxx
if(expr == 0 && frac != 0){
return 0;
}
// normalize
// M 1.xxxxxxx
//
if(expr > 0 && expr < 255){
int E = expr - 127;
frac = frac | (1<<23);
if(E > 31){
return 1 << 31;
} else if (E < 0){
return 0;
}
if(E >= 23){
frac <<= (E-23);
} else {
frac >>= (23-E);
}
if(sign){
return ~frac + 1;
} else {
return frac;
}
}
}floatPower2
If y is too tiny, return 0; conversely, if y is too big, return INF.
/*
* 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
*/
unsigned floatPower2(int x) {
int INF = 0xff<<23;
int exp = x + 127;
if(x<-23) return 0
if(exp<=0 && x>-23) return 0x1 << (x+149);
if(exp>=255) return INF;
return exp <<23;
}