bitXor
1
2
3
4
5
6
7
8
9
10
11
12
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
int bitXor(int x, int y) {
int a = ~((~x) & y);
int b = ~((~y) & x);
return ~(a&b);
}
由于所有运算都是按位的，考虑一位即可
设计：x&(~y)
| y/x | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 0 |
对称的，有：
（~x)&y
| y/x | 0 | 1 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 0 |
二者取反后与起来，再取反就是答案。
tmin
1
2
3
4
5
6
7
8
9
10
11
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
int x=(1<<31);
return x;
}
比较容易
isTmax
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
* 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 n1=~0;
int tmp=!(((x+1)^x)^n1);
tmp=tmp&(!(!(x^n1)));
return tmp;
}
自己想的一个怪方法…
!(a^b) : a == b
!(!(a^b)) : a != b（这里需要两次 ! 来保证结果为 0 或 1
~0 : -1
我们判断 x^(x+1) 是否等于 -1
可以发现这样的 x 只能是 Max 或者 -1
于是再判断下 x!=-1 就可以了
allOddBits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* 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 c=0xAA;
int y=c;
y=(y<<8)+c;
y=(y<<8)+c;
y=(y<<8)+c;
return !((x&y)^y);
}
令 y= 0xAAAAAAAA
判断 x&y == y
negate
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;
}
利用 x+~x= -1
-x = ~x+1
isAsciiDigit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 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 neg=1<<31;
int l=0x30,r=0x39;
int r1=x+(~l+1),r2=r+(~x+1);
return (!(r1&neg))&(!(r2&neg));
}
!(x&(1«31)) : x >= 0
结合上一题
conditional
1
2
3
4
5
6
7
8
9
10
11
12
/*
* 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 f=!x;
f=~f+1;
return (y&(~f))^(z&f);
}
x=0 f=1-> -1(11111..11)
x=1 f=0 -> 0(00000..00)
然后与运算
isLessOrEqual
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*
* 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 neg=(1<<31);
//magical:y-x can pass the test
int f1=(!(y&neg))&(!(!(x&neg)));//y>=0&&x<=0
int f2=(!(!(y&neg)))&(!(x&neg));//y<=0&&x>=0
return (f1&f2)|((!f2)&(!((y+(~x)+1)&neg)|f1));
}
见 isAsciiDigit
logicalNeg
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
* 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) {
int a=x|(x>>16);
int b=a|(a>>8);
int c=b|(b>>4);
int d=c|(c>>2);
int e=d|(d>>1);
return (e&1)^1;
}
howManyBits
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/* 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 neg=(1<<31);
int positive=!(x&neg);//x>=0
//x = positive ? x : (~x) -> (-x-1)
int f0 = ~(!positive)+1;
int x0 = ((x&(~f0))^(((~x))&f0));
int cnt=0;
int ans;
//int eqneg;
int eqzero;
int eqn1;
int tmp;
//16
//cnt= x>=v ? cnt:cnt+16
int v=1<<cnt+16;
int fl=!((x0+(~v)+1)&neg);
f0 = ~(!fl)+1;
cnt = cnt+(16&(~f0));
//8
v=1<<cnt+8;
fl=!((x0+(~v)+1)&neg);
f0 = ~(!fl)+1;
cnt = cnt+(8&(~f0));
//4
v=1<<cnt+4;
fl=!((x0+(~v)+1)&neg);
f0 = ~(!fl)+1;
cnt = cnt+(4&(~f0));
//2
v=1<<cnt+2;
fl=!((x0+(~v)+1)&neg);
f0 = ~(!fl)+1;
cnt = cnt+(2&(~f0));
//1
v=1<<cnt+1;
fl=!((x0+(~v)+1)&neg);
f0 = ~(!fl)+1;
cnt = cnt+(1&(~f0));
ans=cnt+2;
//ans=eqneg?32:ans
// eqneg=!(x^neg);
// f0 = ~(!eqneg)+1;
// ans = ((32&(~f0))^(ans&f0));
//ans=eqzero?1:ans
eqzero=(!x);
//f0 = ~(!eqzero)+1;
//ans = ((1&(~f0))^(ans&f0));
// ans=eqn1?1:ans
eqn1=!(x^(~0));
//f0 = ~(!eqn1)+1;
//ans = ((1&(~f0))^(ans&f0));
tmp=eqzero|eqn1;
f0 = ~(!tmp)+1;
ans = ((1&(~f0))^(ans&f0));
return ans;
}
这个有点难，我写了一晚上
思路 ：$w+1$ 位补码可以表示的范围是$[-2^w, 2^w-1]$
先考虑 $x>0$ , 需要求出 $w$ 使得 $2^w \leqslant x \leqslant 2^{w+1} -1$
用类似二进制位的想法： 设置一个累加器 cnt，依次尝试 v=16, 8, 4, 2, 1, 如果 x>= 1«v+cnt ,就把 cnt 加上 v
如果 $x<0$ , 我们希望 $2^w \leqslant -x-1 \leqslant 2^{w+1} -1 $ ,这样才有
$-2^{w+1} \leqslant x \leqslant -2^{w} -1$
实现就使用 isLessOrEqual 和 conditional 的技巧就好了
floatScale2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
* 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) {
int e=0;
int frac=0;
int i;
for(i=30;i>=23;i--){
e<<=1;
if(uf&(1<<i))e++;
}
for(i=22;i>=0;i--){
frac<<=1;
if(uf&(1<<i))frac++;
}
if(e==255)return uf;
if(e==0){
uf=uf^frac;
frac<<=1;
uf=uf^frac;
}
else {
uf=uf^(e<<23);
e++;
if(e==255)uf=uf^frac;
uf=uf^(e<<23);
}
return uf;
}
比较容易，按照浮点数定义做就可以了
注意非规格化的数转换成规格化的数是很自然的，进位的1刚刚好成为e=1，同时f最高位的1被减掉
floatFloat2Int
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
* 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 s=(uf&(1<<31));
int e=0;
int frac=0;
int bias=(1<<7)-1;
int i;
int exp;
int r;
for(i=30;i>=23;i--){
e<<=1;
if(uf&(1<<i))e++;
}
for(i=22;i>=0;i--){
frac<<=1;
if(uf&(1<<i))frac++;
}
exp=e-bias;
if(exp<0)return 0;
if(exp>=31)return 0x80000000u;
r=exp-22;
frac=frac+(1<<22);
if(r>=0)frac<<=r;
else frac>>=-r;
return s?-frac:frac;
}
比较容易
####
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
* 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 e;
int bias=(1<<7)-1;
if(x<-149)return 0;
if(x<=-127)return 1<<(149+x);
if(x>=128)return (255<<23);
e=x+bias;
return e<<23;
}
容易，但气人的是他一直超时，然后发现是时限太小了
