/*天下文章一大抄，你抄我抄大家抄，只是学习笔记，别介意  ~>_<~+ */

　　&(按位与)、|(按位或)、^(按位异或)、~ (按位取反)。
    其中，按位取反运算符是单目运算符，其余均为双目运算符。
    位运算符的优先级从高到低，依次为~、&、^、|，
    其中~的结合方向自右至左，且优先级高于算术运算符，其余运算符的结合方向都是自左至右，且优先级低于关系运算符。

位运算应用口诀 

清零取反要用与，某位置一可用或
若要取反和交换，轻轻松松用异或

                                                                                       　　　　　　　　　　　　　　　　（2）表示二进制数
移位运算
要点   1 它们都是双目运算符，两个运算分量都是【整形】，结果也是【整形】。
         2 "<<" 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。

　　　　　　按位左移。将一个运算量的各位（二进制表示）依次左移若干位，低位补0，高位舍弃不要。

　　　　　　　　　　　　注意：位移操作的右操作数必须小于左操作数的位长度，否则结果未定义。

　　　　如：

　　　　int a=10，c= a<<2;

　　　　即：

　　　　　　　　a：00000000 00000000 00000000 00001010

　　　　　　　　c：00000000 00000000 00000000 00101000

　　　　　　　　所以，c=40。

         3 ">>"右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。

　　　　　　按位右移。将一个运算量的各位（二进制表示）依次右移若干位，低位被移出，高位对无符号数补0，对有符号数要按最高符号位自身填补（即右移后符号不变）。

　　　　　　　　　　　　注意：位移操作的右操作数必须小于左操作数的位长度，否则结果未定义。

　　　　　　　如：

　　　　　　　　　　int a=-10，c= a>>2;

　　　　　　　　即：

　　　　　　　　　　　　　a：00000000 00000000 00000000 00001010

　　　　　　　　　　a的补码：11111111 11111111 11111111 11110110

　　　　　　　　　　c的补码：11111111 11111111 11111111 11111101

　　　　　　　　　　c的原码：10000000 00000000 00000000 00000011

　　　　　　　　　　　所以，c=-3。

　　移位运算的算数规律：

　　　　　在一定的取值范围内（高位不能移出二进制数的有效数字1），将一个整数（无论是正数还是负数）左移1位相当于乘以2；

　　　　　　 右移运算没有取值范围的限定，但有正负数之别。对于正数，右移1位相当于除以2，小数部分截掉；对于负 数，右移1位相当于除以2；小数部分四舍五入。

　　　　　　 由于计算机做移位比做乘法快得多，编译器可以利用这一点进行优化。

位运算符的应用 (源操作数s 掩码mask)
(1) 按位与 “  &　”

按位与运算将两个运算分量的对应位按位遵照以下规则进行计算：
     0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1。
即同为 1 的位，结果为 1，否则结果为 0。
     1 清零特定位 (mask中特定位置0，其它位为1，s=s&mask)　　　

　　　　　　若想对一个存储单元清零，即使其全部二进制位为0，只要找一个二进制数，其中各个位符合一下条件：

　　　　　　原来的数中为1的位，新数中相应位为0。然后使二者进行&运算，即可达到清零目的。
　　　　　　例：原数为43，即00101011（2），另找一个数，设它为148，即10010100（2），将两者按位与运算：
 　　　　　　　　 00101011（2）
　　　　　　　&   10010100（2）
 　　　　　　　　 00000000（2）
     2 取某数中指定位 (mask中特定位置1，其它位为0，s=s&mask)

      　　   若有一个整数a(2byte),想要取其中的低字节，只需要将a与8个1按位与即可。
　　　　　　a 00101100 10101100
　　　　　　b 00000000 11111111
　　　　　　c 00000000 10101100

　  3 保留指定位：
　　　　　　与一个数进行“按位与”运算，此数在该位取1.
　　　　　　例如：有一数84，即01010100（2），想把其中从左边算起的第3，4，5，7，8位保留下来，运算如下：
 　　　　　　 01010100(2)
　　　　　　&00111011(2)
 　　　　　　 00010000(2)
　　　　　　即：a=84,b=59
    　　　　　　  c=a&b=16
(2) 按位或 “  |  ”

按位或运算将两个运算分量的对应位按位遵照以下规则进行计算：
     0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1
即只要有1个是1的位，结果为1，否则为0。

　　两个相应的二进制位中只要有一个为1，该位的结果值为1。借用逻辑学中或运算的话来说就是，一真为真
      常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s|mask)

　　　　例如：60（8）|17（8）,将八进制60与八进制17进行按位或运算。
 　　　　 00110000
　　　　| 00001111
 　　　　 00111111

　　应用：按位或运算常用来对一个数据的某些位定值为1。例如：如果想使一个数a的低4位改为1，则只需要将a与17（8）进行按位或运算即可。

(3) 位异或 “  ^  “

按位异或运算将两个运算分量的对应位按位遵照以下规则进行计算：
     0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0
即相应位的值相同的，结果为 0，不相同的结果为 1。

　　应用：
　　　　（1）使特定位翻转
　　　　　　　　设有数01111010（2），想使其低4位翻转，即1变0，0变1.可以将其与00001111（2）进行“异或”运算，

　　　　　　　　即：
　　　　　　　　　　  01111010
　　　　　　　　　　^00001111
　　　　　　　　　　  01110101
　　　　　　　　运算结果的低４位正好是原数低４位的翻转。可见，要使哪几位翻转就将与其进行∧运算的该几位置为１即可。
　　　　(２)与0相“异或”，保留原值
　　　　　　　　例如：012^00=012
      　　　　　　　   00001010
       　　　　　　^   00000000
        　　　　　　　 00001010
　　　　　　　　因为原数中的1与0进行异或运算得1，0^0得0，故保留原数。
　　　　(３) 交换两个值，不用临时变量
　　　　　　　　例如：ａ＝３，即11（2）；ｂ＝４，即100（2）。
　　　　　　　　想将ａ和ｂ的值互换，可以用以下赋值语句实现：
    　　　　　　　　ａ＝a∧b;
    　　　　　　　　ｂ＝b∧a;
    　　　　　　　　ａ＝a∧b;

　　　　　　　　ａ＝011(2)
    　　　　　　　　（∧）ｂ＝100(2)
　　　　　　　　ａ＝111(2)（a∧b的结果，a已变成７）
   　　　　　　　　 （∧）ｂ＝100(2)
　　　　　　　　ｂ＝011(2)（b∧a的结果，b已变成３）
   　　 　　　　　　（∧）ａ＝111(2)

　　　　　　　　ａ＝100（2）（a∧b的结果，a已变成４）

异或运算的意思是求两个运算分量相应位值是否相异，相异的为1，相同的为0。

按位异或运算的典型用法是求一个位串信息的某几位信息的反。

如欲求整型变量j 的最右4位信息的反，用逻辑异或运算017^j，就能求得j最右4位的信息的反,即原来为1的位，结果是0,原来为0的位，结果是1。

4、“取反”运算符（~）
　　按位取反运算是单目运算，用来求一个位串信息按位的反，即哪些为0的位，结果是1，而哪些为1的位，结果是0。例如, ~7的结果为0xfff8。
     取反运算常用来生成与系统实现无关的常数。如要将变量x最低6位置成0，其余位不变，可用代码x = x & ~077实现。以上代码与整数x用2个字节还是用4个字节实现无关。
二进制补码运算公式：
  -x    =  ~x + 1 = ~(x-1)
   ~x  =  -x-1 
-(~x) =  x+1
~(-x) =  x-1
x+y   =  x - ~y - 1 = (x|y)+(x&y) 
x-y    =  x + ~y + 1 = (x|~y)-(~x&y) 
x^y   =  (x|y)-(x&y)
x|y    =  (x&~y)+y
x&y   =  (~x|y)-~x
x==y:    ~(x-y|y-x)
x!=y:    x-y|y-x
x< y:    (x-y)^((x^y)&((x-y)^x))
x<=y:    (x|~y)&((x^y)|~(y-x))
x< y:    (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y:    (~x|y)&((x^y)|~(y-x))//无符号x,y比较
应用举例
(1) 判断int型变量a是奇数还是偶数           
       a&1   =   0 偶数
       a&1   =   1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1
(3) 将int型变量a的第k位清0，　　　　　　　　　　 即a=a&~(1<<k)
(4) 将int型变量a的第k位置1， 　　　　　　　　　　即a=a|(1<<k)
(5) int型变量循环左移k次，　　　　　　　　　　　 即a=a<<k|a>>16-k   (设sizeof(int)=16)
(6) int型变量a循环右移k次，　　　　　　　　　　　即a=a>>k|a<<16-k   (设sizeof(int)=16)
(7)整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y)   //返回X,Y 的平均值
{   
     return (x&y)+((x^y)>>1);
}
(8)判断一个整数是不是2的幂,对于一个数 x >= 0，判断他是不是2的幂
boolean power2(int x)
{
     return ((x&(x-1))==0)&&(x!=0)；
}
(9)不用temp交换两个整数
void swap(int x , int y)
{

　　x ^= y;
      y ^= x;
      x ^= y;
}
(10)计算绝对值
int abs( int x )
{
　　int y ;
　　y = x >> 31 ;
　　return (x^y)-y ;        //or: (x+y)^y
}
(11)取模运算转化成位运算 (在不产生溢出的情况下)
         a % (2^n) 等价于 a & (2^n - 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下)
         a * (2^n) 等价于 a<< n
(13)除法运算转化成位运算 (在不产生溢出的情况下)
         a / (2^n) 等价于 a>> n
        例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1       
(15) if (x == a) x= b;
　　          else x= a;
　　      等价于 x= a ^ b ^ x;

(16) x 的 相反数 表示为 (~x+1)

移位运算与位运算结合能实现许多与位串运算有关的复杂计算。设变量的位自右至左顺序编号，自0位至15位，有关指定位的表达式是不超过15的正整数。以下各代码分别有它们右边注释所示的意义：
     ~（~0 << n）　　　　　　　　　　　　　　   /* 实现最低n位为1，其余位为0的位串信息 */

     (x >> (1+p-n)) & ~(~0 << n)　　　　　　   /* 截取变量x自p位开始的右边n位的信息 */

     new |= ((old >> row) & 1) << (15 – k)   　 /* 截取old变量第row位，并将该位信息装配到变量new的第15-k位 */

     s &= ~(1 << j) 　　　　　　　　　　　　　　/* 将变量s的第j位置成0，其余位不变 */

     for(j = 0; ((1 << j) & s) == 0; j++) ;　　　 /* 设s不等于全0，代码寻找最右边为1的位的序号j */