黑马程序员技术交流社区
标题: 位运算讲解与部分应用演示 [打印本页]
作者: 坚持努力wbj 时间: 2016-8-30 17:09
标题: 位运算讲解与部分应用演示
一、有关位运算的基础知识总结
位运算包括：&(与)、|(或)、^(异或)、~(取反)、>>(右移)、<<(左移)
环境预设：32位机下面，int占2个字节，有符号
int a = 11;
int b = 1000;
(a)2 = (00000000 00001011 )2 //a的二进制表示
(b)2 = (00000011 11101000 )2 //b的二进制表示
a&b =(00000000 00001000 )2 =(8)10 //一一为一，其它为0
a|b = (00000011 11101011 )2 =(1003)10 //有一为一，零零为0
a^b = (00000011 11100011 )2 =(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自己去查((11111111)2=(2^7+2^6+2^5+2^4+2^3+2^2+2^1+1)10=(1+2+4+8+16+32+64+128)10=(255)
)。现在要划分子网，那么我们就要从表示主机的那个字节也就是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)2 = (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是不是我们想要的结果了呢？言至于此，无需再言！
这个例子有点难于理解.但是经过我的分解应该还算好理解了，弄懂这个例子相信你的位运算已经登入大门了。
例3.《有关集合算法的实现一些学习笔记》中的"算法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进行以为以定位到该位的操作
假如1字节为宽度
1：0000 0001
要定位到第3（k=1，2，3，4。。。。）位
左移2（k-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 )
也可以a=a^(1<<k);k=0,1,2,3,…
(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);
}
解释：
2的n次幂2进制为1后边n个0；减1后二进制位n个1，相与为零；x=0也可以满足以上运算，但0不是2的幂
(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)
Eg：n=3
2^3的2进制：1000
某个数对2^3取模，将他换为2进制，后3位就是模对应的2进制；
2^n-1二进制位111，与原素二进制与后得到的恰好是模
(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 << n1
(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
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |