算法通关村第十一关—理解位运算的规则(青铜)

发布时间:2024年01月13日

???????理解位运算的规则

一、与、或、异或和取反

?与运算的符号是&,运算规则是:对于每个二进制位,当两个数对应的位都为1时,结果才为1,否则结果为0。
?或运算的符号是,运算规则是:对于每个二进制位,当两个数对应的位都为0时,结果才为0,否则结果为1。
?异或运算的符号是⊕(在代码中用∧表示异或),运算规则是:对于每个二进制位,当两个数对应的位相同时,结果为0,否则结果为1。
?取反运算的符号是~,运算规则是:对一个数的每个二进制位进行取反操作,0变成1,1变成0。

0&0=0
0&1=0
1&0=0
1&1=1

0|0=0
0|1=1
1|0=1
1|1=1

00=0
01=1
10=1
11=0

?以下例子显示上述四种位运算符的运算结果,参与运算的数字都采用有符号的8位二进制表示。
?46的二进制表示是00101110,51的二进制表示是00110011。考虑以下位运算的结果。
46&51的结果是34,对应的二进制表示是00100010。
46|51的结果是63,对应的二进制表示是00111111。
46⊕51的结果是29,对应的二进制表示是00011101。
~46的结果是一47,对应的二进制表示是11010001。
~51的结果是一52,对应的二进制表示是11001100。

二、移位运算

?移位运算按照移位方向分类可以分成左移和右移,按照是否带符号分类可以分成算术移位和逻辑移位。
原始:0000 0110 6
右移一次:0000 0011 3 相当于除以2
左移一次:0000 1100 12相当于乘以2

?左移运算的符号是<<,左移运算时,将全部二进制位向左移动若干位,高位丢弃,低位补0。对于左移运算,算术移位和逻辑移位是相同的。
?右移运算的符号是>>。右移运算时,将全部二进制位向右移动若干位,低位丢弃,高位的补位由算术移位或逻辑移位决定:
1.算术右移时,高位补最高位;
2.逻辑右移时,高位补0。
?以下例子显示移位运算的运算结果,参与运算的数字都采用有符号的8位二进制表示。

示例1:29的二进制表示是00011101。29左移2位的结果是116,对应的二进制表示是
01110100;29左移3位的结果是一24,对应的二进制表示是11101000。

示例2:50的二进制表示是00110010。50右移1位的结果是25,对应的二进制表示是00011001;50右移2位的结果是12,对应的二进制表示是00001100。对于0和正数,算术右移和逻辑右移的结果是相同的。

示例3:-50的二进制表示是11001110(补码)。-50算术右移2位的结果是一13,对应的二进制表示是11110011;一50逻辑右移2位的结果是51,对应的二进制表示是00110011。

右移运算中的算术移位和逻辑移位是不同的,计算机内部的右移运算采取的是哪一种呢?
对于Java而言,不存在无符号类型,所有的表示整数的类型都是有符号类型,因此需要区分算术右移和逻辑右移。在Java中,算术右移的符号是>>,逻辑右移的符号是>>>。

三、移位运算与乘除法的关系

?观察上面的例子可以看到,移位运算可以实现乘除操作。由于计算机的底层的一切运算都是基于位运算实现的,因此使用移位运算实现乘除法的效率显著高于直接乘除法的。
?左移运算对应乘法运算。将一个数左移k位,等价于将这个数乘以2k。例如,29左移2位的结果是116,等价于29×4。当乘数不是2的整数次幂时,可以将乘数拆成若干项2的整数次幂之和,例如,a×6等价于(a<<2)+(a<<1)。对于任意整数,乘法运算都可以用左移运算实现,但是需要注意溢出的情况,例如在8位二进制表示下,29左移3位就会出现溢出。
?算术右移运算对应除法运算,将一个数右移k位,相当于将这个数除以2k。例如,50右移2位的结果是12,等价于50/4,结果向下取整。
?从程序实现的角度,考虑程序中的整数除法,是否可以说,将一个数(算术)右移k位,和将这个数除以2k等价?对于0和正数,上述说法是成立的,整数除法是向0取整,右移运算是向下取整,也是向0取整。但是对于负数,上述说法就不成立了,整数除法是向0取整,右移运算是向下取整,两者就不相同了。例如,(-50)>>2的结果是-13,而(-50)/4的结果是-12,两者是不相等的。因此,将一个数(算术)右移k位,和将这个数除以2k是不等价的。算法出题这早就考虑到了这一点,因此在大部分算法题都将测试数据限制在正数和0的情况,因此可以放心的左移或者右移。

四、位运算常用技巧

?位运算的性质有很多,此处列举一些常见性质,假设以下出现的变量都是有符号整数。
幂等律:a&a=a,a|a=a(注意异或不满足幂等律);
交换律:a&b=b&a,a|b=b|a,a⊕b=b⊕a;
结合律:(a&b)&c=a&(b&c),(a|b)|c=a|(b|c),(a⊕b)⊕c=a⊕(b⊕c);
分配律:(a&b)|c=(a|c)&(b|c),(a|b)&c=(a&c)|(b&c),(a⊕b)&c=(a&c)⊕(b&c);
德摩根律:(a&b)=(a)|(b),(a|b)=(a)&(b);
取反运算性质:-1=0,-a=(a-1);
与运算性质:a&0=0,a&(-1)=a,a&(~a)=0;
或运算性质:a|0=a;
异或运算性质:a⊕0=a,a⊕a=0;

根据上面的性质,可以得到很多处理技巧,这里列举几个:
a&(a-1)的结果为将a的二进制表示的最后一个1变成0;
(补码)a&(-a)的结果为只保x留a的二进制表示的最后一个1,其余的1都变成0。
?处理位操作时,还有很多技巧,不要死记硬背,理解其原理对解决相关问题有很大帮助。下面的示例中,1s和0s分别表示与x等长的一串1和一串0:

x^0s=x
x^1s=~x
x^x=0

x&0s=0s
x&1s=x
x&x=x

x|0s=x
x|1s=1s
x|x=x

?而如何获取、设置和更新某个位的数据,也有固定的套路。例如:
1.获取
?该方法是将1左移i位,得到形如00010000的值。接着对这个值与num执行“位与”操作,从而将位之外的所有位清零,最后检查该结果是否为零。不为零说明位为1,否则位为0。代码如下:

boolean getBit(int num,int i){
	return ((num&(1<<i))!=0); //左移使低位自动补0,高位没有数字,也默认为0
}

2.设置(将某一位设置为1)
?setBit先将1左移i位,得到形如00010000的值,接着对这个值和num执行”位或“操作,这样只会改变i位的数据。这样除i位外的位均为零,故不会影响um的其余位。代码如下:

int setBit(int num,int i){
    return num | (1 << i);
}

3.清零(将某一位设置为0)
?该方法与setBit相反,首先将1左移位获得形如00010000的值,对这个值取反进而得到类似11101111的值,接着对该值和num执行”位与“,故而不会影响到num的其余位,只会清零位。

int clearBit(int num int i){
	int mask = ~(1<<i);
	return num & mask;
)

4.更新
?这个方法是将setBit和clearBit合二为一,首先用诸如11101111的值将num的第i位清零。接着将待写入值v左移i位,得到一个i位为v但其余位都为0的数。最后对之前的结果执行”位或“操作,v为这num的i位更新为1,否则为0:

int updateBit(int num,int i,int v){
	int mask=~(1<<i);
	return (num & mask) | (v << i);
}
文章来源:https://blog.csdn.net/m0_73709096/article/details/135571081
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。