位运算基础版(经典)

位操作基础基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如下所示：符号描述运算规则&与两个位都为1时，结果才为1|或两个位都为0时，结果才为0^异或两个位相同为0，相异为1~取反0变1，1变0左移各二进位全部左移若干位，高位丢弃，低位补0右移各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）注意以下几点：1.在这6种操作符，只有~取反是单目操作符，其它5种都是双目操作符。2.位操作只能用于整形数据，其他类型进行位操作会被编译器报错。3.对于移位操作，在微软的VC6.0和VS2008编译器都是采取算术称位即算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中逻辑移位的高位补0而算术移位的高位是补符号位。如下面代码会输出-4和3。位操作应用1.位运算的简单应用表达式位运算等价x+y(x|y)+(x&y)x-y(x|~y)-(~x&y)x^y(x|y)-(x&y)x|y(x&~y)+yx&y(~x|y)-~xx==y(x-y|y-x)x!=yx-y|y-xxy(x-y)^((x^y)&((x-y)^x))xy(~x&y)|((~x|y)&(x-y))//无符号x,y比较x=y(~x|y)&((x^y)|~(y-x))//无符号x,y比较2.判断奇偶只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if(a&1==0)代替if(a%2==0)来判断a是不是偶数。可以得到如下代码：voidisEven(intn){//判断偶数if((n&1)==0){//注意优先级，位运算优先级很低coutEvenendl;}else{coutOddendl;}}3.不使用第三变量的两数交换1voidswap(int&a,int&b){23if(a!=b){4a^=b;5b^=a;6a^=b;7}8}可以这样理解：1）a^=b即a=(a^b);2）b^=a即b=b^(a^b)，由于^运算满足交换律，b^(a^b)=b^b^a。由于一个数和自己异或的结果为0并且任何数与0异或都会不变的，所以此时b被赋上了a的值。3）a^=b就是a=a^b，由于前面二步可知a=(a^b)，b=a，所以a=a^b即a=(a^b)^a。故a会被赋上b的值。再来个实例说明下以加深印象。inta=13,b=6;a的二进制为13=8+4+1=1101(二进制)b的二进制为6=4+2=110(二进制)第一步a^=ba=1101^110=1011;第二步b^=ab=110^1011=1101;即b=13第三步a^=ba=1011^1101=110;即a=54.改变符号（好用）变换符号就是正数变成负数，负数变成正数。可以利用求补码的方法（按位取反+1）来处理。如对于-11和11，可以通过下面的变换方法将-11变成1111110101(二进制)–取反-00001010(二进制)–加1-00001011(二进制)同样可以这样的将11变成-1100001011(二进制)–取反-00001010(二进制)–加1-11110101(二进制)可以得到如下代码：1intchangeSign(intn){2return~n+1;3}5.取绝对值对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反,因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值因此可以得到如下代码：1intabs(intn){//正数n31为0；负数n31为12return(n^(n31))-(n31);//负数取反加一，即取补码取负3}6.高低位互换给出一个32位的无符号整数。称这个二进制数的前16位为“高位”，后16位为“低位”。现在写一程序将它的高低位交换。例如，数0x1234ABCD用二进制表示为：00010010001101001010101111001101将它的高低位进行交换，我们得到了一个新的二进制数：10101011110011010001001000110100它即是0xABCD1234。这个问题用位操作解决起来非常方便，设x=0x1234ABCD由于x为无符号数，右移时会执行逻辑右移即高位补0，因此x右移16位将得到00000000000000000001001000110100。而x左移8位将得到00000000000000001010101111001101。可以发现只要将x16与x16这两个数相或就可以得到结果。代码如下intexchangeBits(unsignedintn){return(n16)|(n16);}7.二进制逆序我们知道如何对字符串求逆序，现在要求计算二进制的逆序，如数34520用二进制表示为：10000110110110000000000000000000将它逆序，我们得到了一个新的二进制数：00000000000000000001101101100001它即是十进制的7009。回顾下字符串的逆序的方法，可以从字符串的首尾开始，依次交换两端的数据。在二进制逆序我们也可以用这种方法，但运用位操作的高低位交换来处理二进制逆序将会得到更简洁的方法。类似于归并排序的分组处理，可以通过下面4步得到32位数据的二进制逆序：第一步：每2位为一组，组内高低位交换00000000000000001000011011011000→00000000000000000100100111100100第二步：每4位为一组，组内高低位交换00000000000000000100100111100100→00000000000000000001011010110001第三步：每8位为一组，组内高低位交换00000000000000000001011010110001→00000000000000000110000100011011第四步：每16位为一组，组内高低位交换00000000000000000110000100011011→01100001000110110000000000000000对第一步，可以依次取出每2位作一组，再组内高低位交换，这样有点麻烦，下面介绍一种非常有技巧的方法。先分别取1000011011011000的奇数位和偶数位，空位以下划线表示。原数00000000000000001000011011011000奇数位0_0_0_0_0_0_0_0_1_0_0_1_1_0_1_0_偶数位_0_0_0_0_0_0_0_0_0_0_1_0_1_1_0_0将下划线用0填充，可得原数00000000000000001000011011011000奇数位00000000000000001000001010001000偶数位00000000000000000000010001010000再将奇数位右移一位，偶数位左移一位，此时将这两个数据相与即可以达到奇偶位上数据交换的效果了。原数00000000000000001000011011011000奇数位右移00000000000000000100001101101100偶数位左移00000000000000000000100010100000相或得到00000000000000000100100011100100可以看出，结果完全达到了奇偶位的数据交换，再来考虑代码的实现——取x的奇数位并将偶数位用0填充用代码实现就是x&0xAAAAAAAA取x的偶数位并将奇数位用0填充用代码实现就是x&0×55555555因此，第一步就用代码实现就是：x=((x&0xAAAAAAAA)1)|((x&0×55555555)1);类似可以得到如下代码：1intrevertBits(unsignedintn){2n=((n&0xAAAAAAAA)1)|((n&0x55555555)1);3n=((n&0xCCCCCCCC)2)|((n&0x33333333)2);4n=((n&0xF0F0F0F0)4)|((n&0x0F0F0F0F)4);5n=((n&0xFF00FF00)8)|((n&0x00FF00FF)8);6n=((n&0xFFFF0000)16)|((n&0x0000FFFF)16);78returnn;9}8.32位整数前导零的个数01intpreZero(unsignedintn){02intcount=0;0304if(n==0)05return(32);06if((n16)==0)07count=count+16;n=n16;08if((n24)==0)09count=count+8;n=n8;10if((n28)==0)11count=count+4;n=n4;12if((n30)==0)13count=count+2;n=n2;14if((n31)==0)15count=count+1;n=n1;1617returncount;18}9.二进制中1的个数方法1：考虑到n-1会把n的二进制表示中最低位的1置0并把其后的所有0置1，同时不改变此位置前的所有位，那么n&(n-1)即可消除这个最低位的1。这样便有了比顺序枚举所有位更快的算法：循环消除最低位的1，循环次数即所求1的个数。此算法的时间复杂度为O(n的二进制表示中的1的个数)，最坏情况下的复杂度O(n的二进制表示的总位数)。1intcount1(unsignedintn){2intcount=0;3while(n){//所有1全部被消除的时候计数完毕4n&=(n-1);5count++;6}7returncount;8}方法2：通过下面四步来计算其二进制中1的个数二进制中1的个数。第一步：每2位为一组，组内高低位相加00000000000000001000011011011000→00000000000000000100010110010100第二步：每4位为一组，组内高低位相加00000000000000000100010110010100→00000000000000000001001000110001第三步：每8位为一组，组内高低位相加00000000000000000001001000110001→00000000000000000000001100000100第四步：每16位为一组，组内高低位相加00000000000000000000001100000100→00000000000000000000000000000111代码如下：1intcount1_2(unsignedintn){2n=((n&0xAAAAAAAA)1)+(n&0x55555555);3n=((n&0xCCCCCCCC)2)+(n&0x33333333);4n=((n&0xF0F0F0F0)4)+(n&0x0F0F0F0F);5n=((n&0xFF00FF00)8)+(n&0x00FF00FF);6n=((n&0xFFFF0000)16)+(n&0x0000FFFF);7returnn;8}