实验过程

bitXor

思路比较简单，即使用~和&实现异或
异或即相同为0不同为1
Y = ~AB + ~BA即可实现
然后把或通过德摩根律变成与即可实现

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

tmin

补码的最小二进制数就是最高位1其余为0

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1 << 31;
}

isTmax

因为返回值只有0和1，所以考虑最后肯定是使用!运算符来实现
然后考虑最大数独有的特点，即0x7fffffff + 1 = 0x80000000 = -2147483648
所以 0x80000000 + 0x7fffffff = -1
所以 0x80000000 + 0x7fffffff + 1 = -1 + 1 = 0
所以 !(0x80000000 + 0x7fffffff + 1) = !(-1 + 1) = 1
综上即 !((x + 1) + x + 1)
这个式子看着就很诡异，只有边界值才满足，但是少考虑了最小边界值0和-1的情况（出错后才意识到），所以加个和0x7fffffff相与的操作即可避免0xffffffff的情况

/*
 * 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 & 0x7fffffff)) + 1);
}

allOddBits

奇数位全为1才能是1，那么0x0 - 0xF 中，只有0xA, 0xB, 0xE, 0xF才满足，即这个数字最小的是0xAAAAAAAA，那么无论这个数是多少，只要满足这个条件，其与0xAAAAAAAA相与后，偶数位一定为0（AH = 1010B），所以如果设这个数满足要求，则与0xAAAAAAAA与运算后，其值一定是0xAAAAAAAA，那么再与0xAAAAAAAA异或后，其值一定为0，取反则为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) {
  // a b e f
  return !((x & 0xAAAAAAAA) ^ 0xAAAAAAAA);
}

negate

无论从二进制数上推还是凭感觉硬试，都挺简单的，以8位来举个例子

5:  00000101
-5: 11111011

无论正数还是负数都等于原来的取反 + 1

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x + 1;
}

isAsciiDigit

思路大体上分为两部分
第一个是前28位，必须是0x3，异或判断即可
第二个是后4位，逻辑如下（或的思维）：
要么最高位是0（范围锁定在0x0 - 0x7）
要么第二三位是0（范围锁定在0x8 - 0x9）
然后用!运算的思维相与即可

/* 
 * 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 >> 4) ^ 0x3)) & (!((x << 28) >> 31) | !((x << 29) >> 30));
}

conditional

实现一个x ? y : z 条件运算符

逻辑是，如果x不为0则返回y，否则z

那么可以用异或来做，思路初步是这样的，因为x是不确定的数，但是在逻辑中只有0和非0，所以我们可以采用两次!!操作符让他变成非0和0的两个仅有的情况(0x00000000和0x00000001)

使用~x + 1可以让两种情况分别为0x00000000和0xffffffff，然后再用异或处理即可

/* 
 * 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) & y) ^ ((~(!x) + 1) & z);
}

未完待续

反馈总结

判断在某个区间擅用异或操作
以二进制的角度看待问题