1. bitXor
/*
* 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 2;
}
思路
将异或的真值表写出来，再用 & | ~ 表示，最后化简
代码
int bitXor(int x, int y) {
/*
int exp1 = ~(x & ~y);
int exp2 = ~(~x & y);
int res = ~(exp1 & exp2);
*/
return ~((~x)&(~y))&(~(x&y));
}
2.tmin
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
int tmin(void) {
return 2;
}
思路
返回二进制补码的最小值，即0x80000000，使用左移操作即可
代码
int tmin(void) {
return 1 << 31;
}
3.isTmax
/*
* 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 2;
}
思路
如果x是二进制补码的最大值0x7fffffff，返回1,否则返回0.
我的思路是将x进行运算，如果是0x7fffffff，运算结果会是一个特殊值，比如全0，而其他数进行运算则不是全0,最后取非。
想到了0x7fffffff + 0x7fffffff + 1 = 0xffffffff，按位取反后为0x0.
但一直有bug调试不出来，调试结果如下：
printf("%x %x %d %d\n", x, x + x + 1, (!(~(x + x + 1))), ~(x + x + 1));
输出：
7fffffff ffffffff 0 0
取了非和没取非的值居然相同
最后参考了这篇博客
代码
int isTmax(int x) {
//printf("%x\n", !(~(0x7fffffff + 0x7fffffff + 1)));
//printf("%x %x %x\n", x, 0x7fffffff, !!~(x+x+1));
//printf("%x %x %d %d\n", x, x + x + 1, (!(~(x + x + 1))), ~(x + x + 1));
int i = x + 1;
int j = x ^ i;
int k = ~j;
return !(k + !i);
}
4. allOddBits
/*
* 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) {
return 2;
}
思路
如果x的所有奇数位都为1则返回1,否则返回0
先构造一个A8 = 0xAAAAAAAA作为掩模，再和x进行与运算，将无关的偶数位置0
将结果和A8异或，若奇数位全为1，结果将为全0，取个非即答案
代码
/*
* 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 AA = 0xAA;
int A4 = (AA << 8) + AA;
int A8 = (A4 << 16) + A4;
return !((x & A8) ^ A8);
}
5. negate
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return 2;
}
思路
返回相反数，即返回-x的补码，取反加一即可
代码
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
int negate(int x) {
return ~x + 1;
}