位运算

编程开发 Heller 343℃ 0评论

一、前言

输入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)

 

八、实例

功能示例位运算
去掉最后一位101101->10110x >> 1
在最后加一个0101101->1011010x < < 1
在最后加一个1101101->1011011x < < 1+1
把最后一位变成 1101100->101101x | 1
把最后一位变成 0101101->101100x | 1-1
最后一位取反101101->101100x ^ 1
把右数第 k 位变成 1101001->101101(k=3 )x | (1 < < (k-1))
把右数第 k 位变成 0101101->101001(k=3 )x & ~ (1 < < (k-1))
右数第 k 位取反101001->101101(k=3 )x ^ (1 < < (k-1))
取末三位1101101->101x & 7
取末 k 位1101101->1101(k=5 )x & ((1 < < k)-1)
取右数第 k 位1101101->1 (k=4)x >> (k-1) & 1
把末k 位变成1101001->101111(k=4 )x | (1 << k-1)
末k 位取反101001->100110(k=4 )x ^ (1 << k-1)
把右边连续的1变成0100101111->100100000x & (x+1)
把右起第一个0变成1100101111->100111111x | (x+1)
把右边连续的0变成111011000->11011111x | (x-1)
取右边连续的1100101111->1111(x ^ (x+1)) >> 1
去掉右起第一个1 的左边100101000->1000x & (x ^ (x-1))
判断奇数(x&1)==1 
判断偶数(x&1)==0 


转载请注明:无名小站 » 位运算

喜欢 (0)or分享 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址