位运算的威力-阿里云开发者社区

开发者社区> 开发与运维> 正文

位运算的威力

简介: 转载至 http://blog.csdn.net/iukey/article/details/7195265 刘伟Derick-IOS应用开发(iPhone iPad 应用、游戏)潇洒的程序员     昨天写了篇有关集合的东西,中间用到了位运算,看起来还是有点纠结的,今天在这里详细解释一下。

转载至 http://blog.csdn.net/iukey/article/details/7195265

刘伟Derick-IOS应用开发(iPhone iPad 应用、游戏)潇洒的程序员

  

 昨天写了篇有关集合的东西,中间用到了位运算,看起来还是有点纠结的,今天在这里详细解释一下。

(欢迎转载,转载请注明出处,谢谢。)
一、有关位运算的基础知识总结
位运算包括:&(与)、|(或)、^(异或)、~(取反)、>>(右移)、<<(左移)
环境预设:32位机下面,int占2个字节,有符号
int a = 11;
int b = 1000;
(a)(00000000 00001011 )2                                            //a的二进制表示
(b)(00000011 11101000 )2                                            //b的二进制表示
a&b =(00000000 00001000 )=(8)10                             //一一为一,其它为0
a|b =  (00000011 11101011 )=(1003)10                    //有一为一,零零为0
a^b = (00000011 11100011 )=(995)10                       //相同为0,不相同为1
~b =   (11111100 00010111 )2 =(-31767)10               //按位取反
b>>3 =  (00000000 01111101 )2 =(125)10                   // 去掉低3位,高位补0
或      =  (11100000 01111101 )2 =(-24701)10           //去掉低3位,高位补1    补0还是1具体情况视编译环境决定
a<<3 =  (00000000 01011000 )2 =(88)10                    //去掉高3位,低位补0

    看了上面的例子,相信你已经明白具体规则了,不明白自己去google。下面讲具体作用。
    位运算应用口诀
清零取数要用与,某位置一可用或
若要取反和交换,轻轻松松用异或

例1.子网掩码
    子网掩码是个啥东东我也就不讲了,计算机科学技术本身就是个非常庞大系统,一个人不可能面面俱到,但是一些基本的尝试还是要懂的,不懂的可以自己去google,也可以等我的相关网络方面的文章。这里只讲与本问有关的应用部分。
    假如我是一个网管,公司内部使用C类地址,现在我要把公司网络划分成5个子网,网络号为192.168.1.0的前三段,那么子掩码怎么填呢?
    我现在先告诉你子网的子网掩码分别怎么填:192.168.1.224。(当然这里还有其他答案,我取的是在子网扩充不超过8个的情况下的每个子网所容纳主机最多的最佳方案)。
    这个怎么来的呢?ip本身是个二进制的东东,为了方便人们设置,我们采用了点分十进制的转换,把32位的ip地址转换成了4个字节的十进制莱表示。比如 192.168.1.213 这个ip地址的二进制表示为:11000000 10101000 00000001 11010101 。对于C类地址默认的前三个字节表示网络号,那么这个网络号就是:11000000 10101000 00000001   ,最后一个字节11010101表示主机号,可以知道这个网络可以容纳的最多主机数为2^8-2,为什么减2自己去查。现在要划分子网,那么我们就要从表示主机的那个字节也就是8个位里面拿出几个位来表示子网号, 几位比较合适呢?这就要看你需要划分多少个子网咯。比如我们现在要划分5个子网,(5)10 = (101)2 ,那么至少就需要3位了,而且最多可以划分2^3 = 8个子网。现在你把224换成二进制看看吧(224)10 = (11100000)2  ,明白了吧,我们可以推断出子网掩码干了什么勾当?不错子网掩码与ip地址做了按位与运算,他的作用就是屏蔽了主机号获取网络号与子网号。如果你明白了这点,你就知道自己在192.168.1.64子网的ip该怎么填了,不会错误滴填成192.168.1.10了。 
    竟然扯到一边去了,讲了半天才讲了一个与运算的应用。

例2. 防止int型变量溢出
    int x = 32760;int y = 32762; 要求求x、y的平均值,要求空间复杂度位O(0)。
    你能用常规方法去解决吗?可以。我不会讲,这里只讲位运算的 方法。
int ave(int x, int y)   //返回X、Y的平均值
{   
     return (x & y) + ( (x^y)>>1 );
}
知识点:>>n 相当于除于2^n ,<<n 相当于乘于2^n .
                 x,y对应位均为1,相加后再除以2还是原来的数,如两个00001000相加后除以2仍得00001000,那么我们把x与y分别分成两个部分来看,两者相同的位分别拿出来 则 :
x = (111111111111000)2 =  (111111111111000)2 +  (000000000000000)2
y =  (111111111111010) (111111111111000)2 +  (000000000000010)2
相同部分我们叫做x1,y1,不同部分我们叫做x2,y2.那么现在(x+y)/2 =(x1+y1)/2 +(x2 + y2)/2 ,因为x1 == y1 ,所以(x1+y1)/2 ==x1 ==y1,
相同部分我们用与运算求出来 x1 = x&y ,不同部分的和我们用^求出来,然后除于2是不是我们想要的结果了呢?言至于此,无需再言!            
这个例子有点难于理解.但是经过我的分解应该还算好理解了,弄懂这个例子相信你的位运算已经登入大门了。

 
算法2. 将整数index的元素插入集合(阅读此例请先阅读该文)
int insert(BitSet* s,int index){
    if(index >=0 && index>>3 < s->size)
        {s->array[index>>3] |= (1<< (index & 7) );return 1}
    return 0;
}
代码详解:index>=0不解释,(index>>3 )< s->size 这个是保证  index  < n 的。因为index<=n-1,所以 index/8 <=(n-1)/8,又因为 index < n+7 ==(n-1) +8,所以index/8 < (n-1)/8 +8/8 == s->size。因为array的下标是0到size-1,index>>3也就是index/8取整也就是index下标所在的字节,index&7  等价于  index & 0000000 00000111 ,就是取index二进制编码的低三位也就是相当于index>>3所剩下的余数,余数对应的十进制就是index所在字节的序号( 这个序号也是从0开始,并且从右至左),所以把1左移相应的位数就是index在n中对应bit了,再把s->array[index>>3]也就是index所在的字节与(1<<(index&7))也就是除了index所在的位以外均为0或运算,这样无论index所对应位原先是什么状态,之后都被置1。这个可能比上一个例子难度大多了,这个需要掌握位向量的相关知识,如果你不能看懂就跳过吧。
 
   以上是我自己的一些学习心得。下面将贴上一些网络上的例子。
 应用举例
(1) 判断int型变量a是奇数还是偶数           
a&1   = 0 偶数
       a&1 =   1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int)),即a>>k&1   (先右移再与1)

(3) 将int型变量a的第k位清0,即a=a&~(1<<k)    (10000 取反后为00001 )

(4) 将int型变量a的第k位置1,即a=a|(1<<k)     

(5) int型变量循环左移k次,即a=a<<k|a>>16-k   (设sizeof(int)=16)
(6) int型变量a循环右移k次,即a=a>>k|a<<16-k   (设sizeof(int)=16)

(7)对于一个数 x >= 0,判断是不是2的幂。

boolean power2(int x)
{
    return ( (x&(x-1))==0) && (x!=0);
}

(8)不用temp交换两个整数
void swap(int x , int y)
{
 x ^= y;
 y ^= x;
 x ^= y;
}

(9)计算绝对值

int abs( int x )
{
 int y ;
 y = x >> 31 ;
 return (x^y)-y ;        //or: (x+y)^y
}

(10)取模运算转化成位运算 (在不产生溢出的情况下)
         a % (2^n) 等价于 a & (2^n - 1)
(11)乘法运算转化成位运算 (在不产生溢出的情况下)
         a * (2^n) 等价于 a<< n
(12)除法运算转化成位运算 (在不产生溢出的情况下)
         a / (2^n) 等价于 a>> n
        例: 12/8 == 12>>3
(13) a % 2 等价于 a & 1       
(14) if (x == a)

                  x= b;
   else      x= a;
        等价于 x= a ^ b ^ x;
(15) x 的 相反数 表示为 (~x+1)
(16)输入2的n次方:1 << 19
(17)乘除2的倍数:千万不要用乘除法,非常拖效率。只要知道左移1位就是乘以2,右移1位就是除以2就行了。比如要算25 * 4,用25 << 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->101001,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)) 
判断奇数       (x&1)==1 
判断偶数        (x&1)==0        

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章