玩转位运算

题目1，考察一个二进制表示的数，奇数位上的数字全部为1时，返回1。否则返回0。比如allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1。

思路，先构造一个奇数位上都为1的数，即0xAAAAAAAA。 任何数，与这个数位与（&）后，奇数位为1的位置仍为1，为0的位置将为0；偶数位上的数将转化为0。再跟这个数异或，则满足要求的数将转化为0，不满足要求的数为非0。取反即可。

int allOddBits(int x) {
  int a = 0xAA | 0xAA << 8;
  int b = a | a << 16; // b = 0xAAAAAAAA
  return !((x&b)^b);
}

题目2，求一个数的相反数，x --> -x

思路，这个题是常识题，~x是x的反码。

int negate(int x) {
  return ~x + 1;
}

题目3，使用位运算求绝对值。

思路，对于正数，不用位运算，返回x即可。对于负数，根据题目2，myAbs(x) = ~x + 1。对一个数求补码，还可以用异或^来表示，即~x = x^-1 , 由于x是负数，那么~x = x ^(x>>31) 。推到如下，sign = flag >> 31, flag表示符号位。基本的思路是找出相同的位运算操作，使用的参数为0，1或-1，然后通过输出参数x，来构造这些数。

x      =    x^0    =     x^0 - 0   =   x^sign - sign  x >= 0
abs(x) = 
     ~x + 1 = x^-1 + 1  =   x^-1 - (-1) =   x^sign - sign  x < 0

int myAbs(int x)  
{  
    int i = x >> 31;  
    return ((x ^ i) - i);  
}

题目4，条件判断。如果x != 0, result = y；如果x = 0, result = z。

思路, 该题最重要的是，通过x构造出一个打开y 或者打开z的开关。所以基本的结构就是

(-1 & y) |  (0 & z)   =  (~!x & y)  |  (!x & z)    x != 0
result =      
    (0 & y)  |  (-1 & z)  =   (x & y)   |  (~x &z)      x = 0

好像很难归结于同一个式子。这里就需要利用一些性质闪转腾挪了，如x = 0时，x = !!x。以及 x = 0时，x与它的相反数相等，即x = ~x + 1。

int conditional(int x, int y, int z) {
  x = !!x; 
  x = ~x + 1; 
  return (x & y) | (~x & z);