位运算
1 位逻辑运算符：
& （位 “与”） and ^ （位 “异或”） | （位 “或”） or ~ （位 “取反”） 2 移位运算符： <<（左移）
>>（右移）
优先级
位“与”、位“或”和位“异或”运算符都是双目运算符，其结合性都是从左向右的，优先级高于逻辑运算符，低于比较运算符，且从高到低依次为&、^、|
-
&运算
//1&1为1否则都为0 0&1 =0; 0&0 =0; 1&0 =0; 1&1 =1; 00111&11100=00100 //& 最常用的操作是二进制取位 x&1->x的二进制&00..1,即取二进制的最末尾 //这可以判断x的奇偶,x二进制末尾位0则是偶数,1则位奇数 -
|运算
0|0=0; 0|1=1; 1|0=1; 1|1=1; 00111|11100=11111 //| 运算通常用于二进制特定位上的无条件赋值，例如一个数|1的结果就是把二进制最末位强行变为1 //如果需要把二进制最末位变成0，对这个数 |1之后再减一就可以了，其实际意义就是把这个数强行变成最近接的偶数 -
^运算
0^1=1; 1^0=1; 1^1=0; 0^0=0; 00111^11100=11011 //可以将^理解位二进制的加法 1+1=0,1+0=1,0+1=1,0+0=0; //性质: (a^b)^c==a^(b^c) a^a=0,a^0=a; //自反性 a^b^b=a^0=a; -
~运算
-
<<运算
//a<<b 表示把a转为二进制后左移b位（在后面添加 b个0）。例如100的二进制表示为1100100，100左移2位后（后面加2个零）：1100100<<2 =110010000 =400，可以看出，a<<b的值实际上就是a乘以2的b次方，因为在二进制数后面添加一个0就相当该数乘以2，2个零即2的2次方 等于4。通常认为a<<1比a*2更快，因为前者是更底层一些的操作。因此程序中乘以2的操作尽量用左移一位来代替 -
>>运算
//和<<相似，a>>b表示二进制右移b位（去掉末b位），相当于a除以2的b次方（取整）。我们经常用>>1来代替 /2（div 2),比如二分查找、堆的插入操作等等。想办法用>>代替除法运算可以使程序的效率大大提高。最大公约数的二进制算法用除以2操作来代替慢的出奇的%（mod）运算，效率可以提高60%。 int a =100; a/4 ==a>>2; -
常见操作表
去掉最后一位 101101->10110 x>>1 在最后加一个0 101101->1011010 x<<1 在最后加一个1 101101->1011011 (x<<1)+1 把最后一位变成1 101100->101101 x | 1 把最后一位变成0 101101->101100 (x |1) - 1 最后一位取反 101101->101100 x ^ 1 把右数第K位变成1 101001->101101,k=3 x | (1<<(k-1)) 把右数第K位变成0 101101->101101,k=3 x & ~(1<<(k-1)) 右数第k位取反 101001->101101,k=3 x ^ (1<<(k-1)) 取末三位 1101101->101 x &7 取末k位 1101101->1101,k=5 x & (1<<k-1) 取右数第k位 1101101->1,k=4 x >> (k-1)&1 把末k位变成1 101001->101111,k=4 x|(1<<k-1) 末k位取反 101001->100110,k=4 x^(1<<k-1) 把右边连续的1变成0 100101111->100100000 x&(x+1) 把右起第一个0变成1 100101111->100111111 x|(x+1) 把右边连续的0变成1 11011000->11011111 x|(x-1) 取右边连续的1 100101111->1111 (x^(x+1))>>1 去掉右起第一个1的左边(树状数组中) 100101000->1000 x&(x^(x-1)) -
原码,反码,补码
前面 所说的位运算都没有涉及负数，都假设这些运算是在unsingned类型（只能表示正数的整型）上进行操作。 但计算机如何处理有正负符号的整型呢？这个设计到补码，反码知识点，请看下面 假设有一 int 类型的数，值为5，那么，我们知道它在计算机中表示为：00000000 00000000 00000000 00000101 5转换成二进制是101，不过int类型的数占用4字节（32位），所以前面填了一堆0。 现在想知道，-5在计算机中如何表示？ 在计算机中，负数以其正值的补码形式表达。 什么叫补码呢？这得从原码，反码说起。 反码，补码 反码和补码的目的就是为了解决负数的问题 在计算机内，定点数有3种表示法：原码、反码和补码 所谓原码就是前面所介绍的二进制定点表示法，即最高位为符号位，“0”表示正，“1”表示负，其余位表示数值的大小。 反码表示法规定：正数的反码与其原码相同；负数的反码是对其原码逐位取反，但符号位除外。 补码表示法规定：正数的补码与其原码相同；负数的补码是在其反码的末位加1。 有原码就可以了，为什么还需要反码和补码？ 反码是用来算补码的，原码和补码都是用在CPU的基本运算里的，比如数据类型是short： 计算5 - 2，并由于实际上CPU没有实现减法电路（注：计算机的硬件结构中只有加法器，所以大部分的运算都必须最终转换为加法，原码没有办法做减法，而在我们使用的汇编、C等其他高级语言中使用的都是原码，原码转换成补码都是在计算机的最底层进行的）。原码计算是 5＋（－2） 0101 ＋1010 ------ 1111 ＝－7？显然出错 所以不管正数还是负数，都使用补码来表示（正数原码和补码是一样的）， 2的补码是1110，然后用5补码+2补码 0101 +1110 ———— 0011 ＝3，正确