《位运算及其应用(ACM).ppt》由会员分享，可在线阅读，更多相关《位运算及其应用(ACM).ppt（9页珍藏版）》请在三一办公上搜索。
1、位运算,六种位运算,&与运算|或运算 异或运算 非运算(求补)右移运算 左移运算,运用这些基本的运算，我们可以解决acm所需的运算,目的 示例表达式去掉最后一位|(101101-10110)|x 1在最后加一个0|(101101-1011010)|x 1011011)|x 101101)|x|1把最后一位变成0|(101101-101100)|x|1-1最后一位取反|(101101-101100)|x 1把右数第k位变成1|(101001-101101,k=3)|x|(1 101001,k=3)|x&(1 101101,k=3)|x(1 101)|x&7取末k位|(1101101-1101,k
2、=5)|x&(1 1,k=4)|x(k-1)&1把末k位变成1|(101001-101111,k=4)|x|(1 100110,k=4)|x(1 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)判断奇数(x&1)=1判断偶数(x&1)=0,(1)判断int型变量a是奇数还是偶数 a&1=0 偶数 a&1=1 奇数
3、(2)取int型变量a的第k位(k=0,1,2sizeof(int)，即ak&1(3)将int型变量a的第k位清0，即a=a&(116-k(设sizeof(int)=16)(6)int型变量a循环右移k次，即a=ak|a16-k(设sizeof(int)=16),乘除法是很消耗时间的，一般情况下位运算的速度要相对快一些。传说用位运算效率提高了60%。,应用1.判断n是否是2的正整数幂,(!(n&(n-1)&n举个例子：如果n=16=10000，n-1=1111那么：10000&1111-0再举一个例子：如果n=256=100000000，n-1=11111111那么：100000000&111
4、11111-0看完上面的两个小例子，相信大家都有一个感性的认识。从理论上讲，如果一个数a他是2的正整数幂，那么a的二进制形式必定为1000.（后面有0个或者多个0），那么结论就很显然了。,应用2.对于正整数的模运算,（注意，负数不能这么算）先说下比较简单的：只要对数左移一位就是乘以2，右移一位就是除以2乘2k众所周知：nk。那么mod 2k呢？（对2的倍数取模）n&(1k)-1)用通俗的言语来描述就是,对2的倍数取模，只要将数与2的倍数-1做按位与运算即可。,应用3.按位异或运算,我们还可以得到一个很诡异的swap操作：a=a b;b=a b;a=a b;自己拿起笔来模拟一下就很清楚的了。想清楚以后可以看一下TOJ 3525,应用4.快速求幂,_int64 FastM(_int64 a,_int64 b,_int64 c)/a的b次对c取模 if(b=0)return 1;_int64 t,sum;t=a%c;sum=1;while(b)if(b,树状数组,TOJ 2711位运算介绍的博客：推荐他的博客（这才是真正的大神）：,
