1
2
3
4
5
6
7
8
9
10/*
* 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) );
}
1
2
3
4
5
6
7
8
9/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 1<<31;
}
1
2
3
4
5
6
7
8
9
10/*
* 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) {
return (!(x+1+x+1))&(!!(x+1));
}
1
2
3
4
5
6
7
8
9
10
11
12
13/*
* 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;
mask+=(mask<<8)+(mask<<16)+(mask<<24);
return !(mask^(mask&x));
}
1
2
3
4
5
6
7
8
9
10/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x+1;
}
1
2
3
4
5
6
7
8
9
10
11
12/*
* 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) {
return !((x+(~0x30+1))>>31) & (x+(~0x3a+1))>>31;
}
1
2
3
4
5
6
7
8
9
10/*
* 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) {
return ((!x+~1+1)&y)|((~!x+1)&z);
}
1
2
3
4
5
6
7
8
9
10
11
12
13/*
* 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 sig_x = x>>31&1;
int sig_y = y>>31&1;
int sig_y_x = ((~x+1+y)>>31)&1;
return (!(sig_x^sig_y)&!sig_y_x)|((sig_x^sig_y)&sig_x);
}
1
2
3
4
5
6
7
8
9
10
11
12/*
* 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+1)^x)&~x)>>31)&1;
return ((~x&~(~x+1))>>31)&1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/* 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
*/
int howManyBits(int x) {
int mask_0=((!x)<<31)>>31;
int mask_neg_1=((!(~x))<<31)>>31;
int bitsNumber=0;
int u_x=(x>>31)&~x | ~(x>>31)&x;
bitsNumber=(!!(u_x>>16))<<4;
bitsNumber=bitsNumber+((!!(u_x>>(bitsNumber+8)))<<3);
bitsNumber=bitsNumber+((!!(u_x>>(bitsNumber+4)))<<2);
bitsNumber=bitsNumber+((!!(u_x>>(bitsNumber+2)))<<1);
bitsNumber=bitsNumber+(!!(u_x>>(bitsNumber+1)));
return (~mask_0)&(~mask_neg_1)&(bitsNumber+2) | mask_0&1 |mask_neg_1&1 ;
}