位运算小结操作

一、前言

输入2 的n 次方： 
如果突然要你输入2 的19 次方，你是不是还要想一下呢？敲个524288 多累啊。用位运算：1 << 19 又快又准。

乘除2 的倍数： 
千万不要用乘除法，非常拖效率。只要知道左移1 位就是乘以2 ，右移1 位就是除以2 就行了。
比如要算 25 * 4 ，用25 << 2 就好啦。

判断偶数： 
a % 2 取模是最常用的判断方法之一。这样要用到除法运算，不好。实际上，还是用位运算解决：a & 1 。效果和a % 2 是一样的，但是要快得多。

对2 的倍数取模： 
类似上面的方法。对2 的倍数取模，只要将数与2 的倍数-1 做与运算就可以了。如：
a % 8 = a & (8-1)
节省乘除法可以提高效率。

判断一个整数是否是处于 0-65535 之间（常用的越界判断）： 
用一般的 (a >= 0) && (a <= 65535) 可能要两次判断。
改用位运算只要一次：
a & ~((1 << 16)-1)
后面的常数是编译时就算好了的。其实只要进行一次与运算就行了。

算掩码： 
比如一个截取低6 位的掩码：0x3F
用位运算这么表示：(1 << 6) - 1
这样也非常好读取掩码，因为掩码的位数直接体现在表达式里。

二、位运算符

位运算方法有七种：

&   与运算： 当两个位都为1 时结果为1 ，其它为0 。

|  或运算： 当两个位都为0 时结果为0 ，其它为1 。

^  异或运算： 当两个位数值不同时结果为1 ，相同为0 。

~  非运算( 求补) ： 位的值为1 时结果为0 ，位的值为0 时结果为1 。

<< 左移运算： 右边空出的位上补0 ，左边的位将从字头挤掉，其值相当于乘2。

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

>>>   无符号右移运算： 右边的位被挤掉，对于左边移出的空位一概补上0 。



三、位运算应用口诀

清零取反要用与，某一位置可用或。

若要取反和交换，轻轻松松用异或。



四、需要注意的问题

1 、优先级

移位运算符, 单目取反运算符的优先级比比较运算符高。但是“& ”、“|”和“^ ”的优先级是比比较运算符低的，这点一定要注意。

如6 & 6 > 4 的结果是0 ， 而不是 true 。(6 & 6) > 4 的结果才是true ，所以要注意勤加括号。

2 、速度

位运算的速度是非常快的，你甚至可以忽略他的耗时，但是毕竟操作肯定是有耗损的。所以，应该尽量使用

“^= ”、“|= ”和“&= ”这样的操作，比如说a ^= b ， 速度比 a = a ^ b快，因为前者是直接在a 上进行操作，而 a = a ^ b 的第二个a ，是一个a 的副本，可见在操作中程序对a 复制了一次，运算的结果又对原来的a 做了一次赋值

3 、范围

要当心移位运算时发生范围溢出。

4 、位数不同的运算数之间的运算规则

　　C 语言中，位运算的对象可以是整型（int ）和字符型（char ）数据。整形数据可以直接转化成二进制数，字符型数据在内存中以它的ASCII 码值存放，也可以转化成二进制数。当两个运算数类型不同时，位数亦会不同。遇到这种情况，系统将自动进行如下处理：将两个运算数右端对齐，再将位数短的一个运算数往高位扩充，即：无符号数和正整数左侧用0 补全; 负数左侧用1 补全；然后对位数相等的两个运算数，按位进行运算。



五、位运算的应用( 源操作数s ，掩码mask) 

1 、按位与 &

清零特定位（mask 中特定位置0 ，其它位为1 ，s=s&mask ）

取某数中指定位（mask 中特定位置1 ，其它位为0 ，s=s&mask ）

2 、按位或 |

常用来将源操作数某些位的数值置1 ，其它位不变。（mask 中特定位置1 ，其它位为0 ，s=s|mask ）

3 、位异或 ^

使特定位的值取反（mask 中特定位置1 ，其它位为0 ，s=s^mask ）

不引入第三变量，交换两个变量（a ，b ）的值

a = a ^ b;

b = a ^ b;

a = a ^ b;



六、二进制补码运算公式

-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 比较



七、应用举例

01 、判断int 型变量a 是奇数还是偶数

a&1 = 0 偶数

a&1 = 1 奇数

02 、取int 型变量a 的第k 位 (k=0,1,2 ……sizeof(int)) ，即a>>k&1

03 、将int 型变量a 的第k 位清0 ，即a=a&~(1<<k)

04 、将int 型变量a 的第k 位置1 ， 即a=a|(1<<k)

05 、int 型变量循环左移k 次，即a=a<<k|a>>16-k ( 设sizeof(int)=16)

06 、int 型变量a 循环右移k 次，即a=a>>k|a<<16-k (设sizeof(int)=16)

07 、整数的平均值

对于两个整数x 、y ，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX ，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：

int average(int x,int y) // 返回X,Y 的平均值

{

    return (x&y)+((x^y)>>1);

}

08 、判断一个整数是不是2 的幂

对于一个数 x >= 0 ，判断它是不是2 的幂

boolean power2(int x)

{

    return ((x&(x-1))==0)&&(x!=0);

}

09 、 不用 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 ;  // 或者return (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)



八、实例