【算法】位运算与优化
刚刚学算法的时候，看到dalao处处用位运算，感觉真的太玄学了，然后直到今天才深入理解了下位运算的操作，其实并没有多么玄学，只不过是利用了计算机本身的性质罢了。
基本概念：
真值：
带符号位的机器数对应的真正数值称为机器数的真值
0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1
原码：
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值
PS：正数的原、反、补码都一样：0的原码跟反码都有两个，因为这里0被分为+0和-0。
反码：
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
补码：
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
PS：0的补码是唯一的，如果机器字长为8那么[0]补=00000000。
移码：
移码最简单了，不管正负数，只要将其补码的符号位取反即可。
例如：X=-101011 , [X]原= 10101011 ，[X]反=11010100，[X]补=11010101，[X]移=01010101
位运算基本运算符：
&：按位与
|：按位或
^：按位异或（相同为1，不同为0）
~：取反
<<：左移
>>：右移
常用位运算优化方法：
1.判断整数奇(1)偶(0)性：
bool IsOdd(int x)//判断是否为奇数{ return x&1;
}
2.乘以或除以2的幂：
列如： 乘以2: x<<1; 乘以2的n次方：x<<n; 除以2：x>>2; 除以2的n次方：x>>n; 变式： 计算2的n次方：2<<(n-1);
3.比较两个数是否相等：
计算两个数的异或值，若等于0，则两数相等。
bool IsEqual(int a,int b)
{ return !(a^b);
}
4.不使用第三方变量交换a，b：
int a,int b; a=a^=a^=a^b;
5.判断两个数是否同号：
!((a^b)>>31);
6.求n的绝对值：
(n^(n>>31))-(n>>31);
7.提取lowbit()：
int lowbit(int x)
{ return x&-x;
}
8.计算整数x和y的平均值，可防止溢出。
int average(int x, int y) //返回X,Y 的平均值 {
return (x&y)+((x^y)>>1);
}
9.判断一个整数n是否为2的幂 2^n：
((x&(x-1))==0)&&(x!=0);
