Problems

bitXor

~ 和 &运算符实现异或

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);
}

a ^ b = (a | ~b) & (a | b) 异或的表示,画出韦恩图更易理解
(
a | ~b) = ~(a & b) 德摩根率

故 a ^ b = (a | ~b) & (a | b) = ~(a & b) & (\~a | ~~b) = (a & b) & \(~a & ~b)

x&y ==> 某一位都为1,~(x&y) ==> 某一位都为0,或者某一位不相同

~x&~y ==> 某一位都为0,~(~x&~y) ==> 某一位都为1,或者某一位不相同

将上边两个式子再按位与,即可得到仅满足“某一位不相同”的01串,即按位异或的结果


tmin

使用位运算获取对2补码的最小int值

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 0x1 << 31;
}

补码最小int值即:只有第一位为1,后边的所有位为0


isTmax

通过位运算计算是否是补码最大值

① 开始的想法

1
2
3
4
5
6
7
8
9
10
11
/*
* 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 max = 0x7FFFFFFF;
return !(x ^ max);
}

由于规定不能使用大于0xFF的数,并且不能移位,所以需要考虑其他方法

1
2
3
4
5
6
7
8
int isTmax(int x) {
int i = x + 1; // 1000...00
x = i + x; // 1111...11
x = ~x; // 0000...00
i = !i; // 0
x = x + i; // 0
return !x;
}

基本思路是将判断补码最大值转化为判断全0

当x是补码最大值,通过前三行的操作,可以将x转化为全0,之后取反即可得到1

不过要注意的是,当x是-1(即11…11),通过前三行也可以得到全0,所以四五行用于排除这种情况


allOddBits

判断所有奇数位是否都为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 + (0xAA << 8);
mask = mask + (mask << 16);
return !((x & mask) ^ mask);
}

构造掩码 010101…0101 即可


negate

不使用 - 操作符,求 -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;
}

isAsciiDigit

计算输入值是否是数字 0-9 的 ASCII 值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 
* 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; // 符号位
int lowerBound = ~0x30; // 小数与之相加后符号位依然为1
int upperBound = ~(sign | 0x39); // 大数与之相加后符号位变为1
// 如果 x = 30 ,加上lowerBound后恰好为全1,所以还要多加1
lowerBound = (sign & (lowerBound + x + 1)) >> 31;
upperBound = (sign & (upperBound + x)) >> 31;
return !(upperBound | lowerBound); // 要求两者均为0
}
  • 上下界设置需要多思索
  • 只关注符号位
  • 注意lowerBound 的加 1

conditional

使用位级运算实现x?y:z三目运算符

1
2
3
4
5
6
7
8
9
10
11
12
/* 
* conditional - same as x ? y : z
* Example: conditional(3,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
int conditional(int x, int y, int z) {
x = !!x; // 0或1
x = ~x + 1; // 全0或全1
return (x & y) | (~x & z);
}
  • 特殊性质:0的相反数是0(全0),1的相反数是-1(全1)