位运算总结

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

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 条评论
登录 后参与评论

相关文章

来自专栏游戏开发那些事

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

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

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

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

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

28380
来自专栏我的技术专栏

细说new与malloc的10点区别

18340
来自专栏北京马哥教育

Python 开发者不得不知的魔术方法(Magic Method)

来源:j_hao104 my.oschina.net/jhao104/blog/779743 介绍 在Python中,所有以“__”双下划线包起来的方法,都统...

30170
来自专栏C语言及其他语言

实例说明

上一节,我们大致总揽了一个简单C程序的框架,程序如下: #include<stdio.h> /*引入头文件*/ int main(void) /*一个简单的C程...

29080
来自专栏wym

18年暑假多校赛第一场 1002

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

9910
来自专栏每日一篇技术文章

Java_面向对象_04

面向对象是Java的核心,面向对象的核心是用人类解决问题的方法对复杂的客观问题进行分析,组织和解答,对于程序员而言,难点在于尽可能正确描述问题的抽象。面向对象的...

9130
来自专栏程序员的知识天地

Python基础为重,成就月薪过万

傻瓜式,傻瓜式的你可以直接点开进行下载,但是智能下载这版本,有的人愿意下载别的版本所以就要用到另外的方法

8720
来自专栏老九学堂

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

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

38460
来自专栏Python攻城狮

Python3.x 常用的新特性字符串编码格式:

7920

扫码关注云+社区

领取腾讯云代金券