文档章节

常用的位运算技巧

o
 osc_wws45aot
发布于 2019/08/20 18:24
字数 1642
阅读 0
收藏 0

常用的位运算技巧

位运算是很多算法优化的基础和实现的条件,极其重要。理解位运算对于一些算法及其优化有着非常重要的意义。本篇随笔讲解位运算的一些基本原理和常用的使用技巧。

注:本篇随笔的所有“运算”均指二进制下的运算,请大家自行理解。


1、与(&)运算

(1)运算法则

两个二进制数进行与&运算,如果对应位都为1则结果为1,否则为0.

(2)技巧及用途

**与运算常常用于二进制下的取位操作。**想要知道二进制下的某位是否是1,就&上这个位数对应的十进制数。假如返回的是这个十进制数本身,则这个位的确是1,反之就是0.

比如:

我们要取第三位是否为1,我们只需要与&上第三位(二进制表示为100)对应的二进制数4,如果返回值为4,就代表第三位为1,反之就是0.

最常用的是取二进制下的最末位,即a&1。这样的技巧可以用于判断奇偶,根据二进制常识,尾数为1则为奇数,反之为偶数。


2、或(|)运算

(1)运算法则

两个二进制数进行或|运算,如果对应位有一个为1,结果就为1.只有在两个数的对应位置都是0的时候,结果才为0.

(2)技巧及用途

或运算常用于二进制特定位的赋值。想把哪个位强行变成1,就用这个数|上这个位数对应的二进制数。

还是上面那个例子,我们想让00000的第三位变成1.即十进制变4,我们直接|上4就可以。

当然,不同于&运算,我们很少用|运算进行任意位赋值。通常来讲,我们只使用a|1把a的最后一位强行变成1,其实质意义是把原数加一。或者使用a|1-1再把它变为0.这个技巧通常用于把它变成它最接近的偶数


3、异或(^)(xor)运算

(1)运算法则

两个二进制数进行异或(^)运算,如果对应位相同,不管是0或者是1,都返回1,反之返回0.

(2)技巧及用途

其实没啥用途...

好吧,我介绍一个性质:一个数经过两次异或之后等于原数。

(很好理解)


4、非(~)运算

(1)运算法则

把给定二进制数全部取反。

(2)技巧及用途

其实没什么运算上的用途,本蒟蒻曾看见一些大佬用这个运算判断输入是否为0...

大约长这个样子:

while(~scanf("%d",&n))

5、左移(<<)运算

(1)运算法则

a<<b表示把a的二进制位向左移动b位,低位用0补上。

(2)技巧及用途

根据二进制的常识,我们会发现,二进制第k位上的数就等于$2^k$。(从0开始计位)

比如,二进制下的100就是$2^{k=2}=4$。

所以我们发现,左移运算a<<b的实质就是$a×2^b$。

左移运算最常用的技巧就是用来代替×2的整数次幂的乘法运算。因为我们普遍认为,位运算是要比四则运算加减乘除及模运算更快一些的运算。


6、右移(>>)运算

(1)运算法则

a>>b就是把a的二进制位向右移动b位,溢出的舍去。

(2)技巧及用途

类比于左移运算,我们发现右移运算就是把a除以2的整数次幂。这就是右移运算的用途——优化除法运算。

这里需要特殊说明的是,右移算法可以用在数学知识中的求最大公约数的程序块上。因为mod运算的效率慢的出奇,所以我们可以用右移运算来进行除以2的操作。据说可以提高百分之60的效率。


7、位运算优先级

位运算的优先级是我们在处理位运算的时候常常要考虑的问题,诚然,我们可以用括号强制位运算的顺序,但是,我们还是应该学会位运算的优先级(这应该是常识)。

位运算的优先级如下:

按位反(~)>位移运算(<<,>>)>按位与(&)>按位异或(^)>按位或(|)


附:位运算在状压DP的用法

众所周知,状压DP就是把状态压缩成一个01串(其实就是一个二进制数),用以减少DP数组的维数。但是我们在DP的时候就要按照01串来进行状态的转移。所以位运算是状压DP的基础知识和必备知识。所以我在本篇随笔的末尾还附上了状压DP中比较常用的操作及其二进制实现的方式。

正文:(本文中的a表示十进制下的整数)

1、获得第i位的数字:(a>>i)&1 或者 a&(1<<i)

很好理解,我们知道可以用&1来提取最后一位的数,那么我们现在要提取第i位数,就直接把第i位数变成最后一位即可(直接右移)。或者,我们可以直接&上1左移i位,也能达到我们的目的。

2、设置第i位为1:a=a|(1<<i)

我们知道强制赋值用|运算,所以就直接强制|上第i位即可。

3、设置第i位为0:a=a&(~(1<<i))

这里比较难以理解。其实很简单,我们知道非~运算是按位取反,(1<<i)非一下就变成了第i为是0,其它全是1的二进制串。这样再一与原数进行&运算,原数的第i位无论是什么都会变成0,而其他位不会改变(实在不明白的可以用纸笔进行推演)。

4、把第i位取反:a=a^(1<<i)

1左移i位之后再进行异或,我们就会发现,如果原数第i位是0,一异或就变成1,否则变成0。

5、取出一个数的最后一个1:a&(-a)

学过树状数组的同学会发现,这就是树状数组的lowbit。事实上,这和树状数组的原理是一样的。我想,不需要我多解释。

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

face-api.js 示例

该示例是基于GitHub的一个开源项目:https://github.com/justadudewhohacks/face-api.js 其核心的库是用js写的,所以它可以在web项目或nodejs 中使用 Html: <!DOCTYPE html><html lang="en......

Canaan_
5分钟前
5
0
树莓派4b + Ubuntu20.04 Server 安装Java8

安装环境: 树莓派4b + Ubuntu20.04 Server 32位 1. 下载jdk https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 2. 解压 tar -zxvf jdk-8u251-linux-arm32-vf......

SummerGao
38分钟前
9
0
项目实战:Qt+OpenCV图像处理与识别算法平台

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
41分钟前
7
0
北京智源大会 | AI + 医疗的下一个十年:从公共卫生预警到人类基因密码破解 道翰天琼认知智能api机器人接口。

医疗事关人身安全,要求极高,容错率极低,因此,知识壁垒和技术壁垒都很高。过去,AI系统更多的是服务于终端,辅助医生诊断、决策。但是,医疗很复杂,直接切入终端问题很多。未来十年,AI+...

jackli2020
45分钟前
11
0
源于HystrixCommandStartStream和RollingCommandMaxConcurrencyStream 的 RxJava demo

其实,最近在工作之余看Hystrix源代码已经有一个多月了, 除了对 HystrixCommandProperties ,HystrixCommand 和AbstractCommand 几个类比较了解以外,其余看山不是山,比较懵, 主要是因为H...

专业写BUG的程序员
48分钟前
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部