位运算总结

用了那么多位运算,这里总结一下把。 先看常用的位运算有哪些吧:

1 & a&b 就是a的二进制形式与b的二进制形式,相同的位置必须两个都是1,那么结果的相应位置就是1,否则就是0. 那么a&b有什么用呢?最简单的,我觉得最常用的就是一个二进制的一部分出来。 例如:111011010011 我要取从左到右的第2到第5位,那怎么办呢? 111011010011 011110000000 只要把下面的数对111011010011 进行&运算就好了,就把1101取出来了。结果是11010000000 那么大家常见的a&1,就是判断偶数的方法,取a的最后一位,是1就是奇数,是0就是偶数。 还有状态压缩DP中经常用到,用来判断两种情况是否有重复的情况

2 | 只有有一个位置为1,那么该位置就是1; 那么 | 运算最常用的就是拼接,怎么拼接呢?以上面的例子对 111011010011 做&位算之后得到11010000000,现在把111011010011 2到5位变成0 得到100001010011,对二者做 | 运算 100001010011 011010000000 就又变成一开始的数。再举个例子11000 和00101做 | 运算 就是拼接在一起答案就是11101

3 ^ 相同位不同则为1,相同则为0。 ^的最常用的就是剪切,例如11111111和11100000做 ^ 运算,那么结果就是00011111 把111剪切掉了。

4 << a << b就表示把a转为二进制后左移b位(在后面添b个0).相当于a乘以2的b次方。 <<的作用自然是向左移动二进制上面的数字 例如 1101<<3 结果是1101000

5 >> a >>b表示二进制右移b位(去掉末b位),相当于a除以2的b次方(取整)>>作用是向右移动二进制上面的数字,例如1101000>>3结果是1101

6 ~ 取反,就是把相应的位置上取反,注意,进行取反的操作的时候 一定要定义成 unsigned 即无符号的,这个可以百度一下,补码的知识。

差不多这些,但是说了这么多,并没有体现到位运算的优势。给一道例题吧,就可以看出位运算强大的优势。 现在有长度最长为15的字符串给你起始字符串和目标字符串,现在你只有两种操作,一个是交换第一个和第二个字符,一个是把最后一个字符放到第一个。字符只有两种。问你最少移动几次可以从起始状态到达目标状态。

大家都可以想到用广搜,如果用string表示状态,但是两种操作将会非常麻烦,弄不好还会超时!因为字符只有两种,二进制压缩可以的。两种操作可以用O(1)的效率解决!!! 假设测试数据的长度为5 只有两个字符a,b ababa aaabb a表示1,b表示0 。那么起始状态压缩成二进制就是10101(22) 第一个操作,把第一个和第二个交换。我们可以把第一位和第二出来,然后剪切掉前两位,交换之后再拼接上 取第一位10101( 22 ) & 10000 ( 16 ) =num1取第二位 10101 & 1000(8)=num2 剪切前两位10101 ^ 11000(24)=num3.那么交换呢?很简单,就是一个向右移动一位,一个向左移动一位。num1>>1, num2<<1.最后拼接:num3 | num2 | num1. 所以最后第一种操作可以写成 (22^24) | ( (22 & 16) >> 1) ) | ( (22 & 8 ) << 1)

第二个操作也很减单了,先把最后一个取出来 然后整体向右移动 1位,取出来的向左移动4位,再拼接起来,自己试一下把。

这下两种操作可以一步解决了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

《算法图解》第二章笔记与课后练习

17510
来自专栏老九学堂

【超全】C语言初学者必须掌握的关键字!

其实小伙伴在写代码的时候,关键字还是用的比较多的,老九主要就平常中用到的常用关键字进行总结,便于小伙伴们更全面的理解其在代码中的意图。 C语言关键字总结 sta...

3656
来自专栏緣來來來

Python爬虫--- 1.4 正则表达式:re库

这里其实就是一个非常简单的删除当前目录下所有txt文件的命令, *号其实就一个 ‘通配符’。表示任何形式的数据。 从这里我们就可以引出正则表达式的概念:

1021
来自专栏小樱的经验随笔

COGS 1299. bplusa【听说比a+b还要水的大水题???】

1299. bplusa ☆   输入文件:bplusa.in   输出文件:bplusa.out 评测插件 时间限制:1 s   内存限制:128 MB ...

2818
来自专栏极客编程

nodejs之async异步编程

在回调函数中进行下一步操作的代码编写风格,常见的如setTimeout函数、ajax请求等等。

912
来自专栏游戏开发那些事

【Unity游戏开发】浅谈Lua和C#中的闭包

  目前在Unity游戏开发中,比较流行的两种语言就是Lua和C#。通常的做法是:C#做些核心的功能和接口供Lua调用,Lua主要做些UI模块和一些业务逻辑。这...

1812
来自专栏我的技术专栏

细说new与malloc的10点区别

1503
来自专栏wym

18年暑假多校赛第一场 1002

http://acm.hdu.edu.cn/showproblem.php?pid=6299

831
来自专栏python3

习题30:While循环

while循环有一个问题,那就是有时它永不结束,不过在其它的情况下你的循环总需要有一个结束点

751
来自专栏北京马哥教育

百度大牛总结十条 Python 面试题检验你的真实水平

学Python最简单的方法是什么?推荐阅读:Python开发工程师成长魔法 概述 Python 是个非常受欢迎的编程语言,随着近些年机器学习、云计算等技术的发...

2756

扫码关注云+社区