专栏首页ACM算法日常唯快不破的01序列——位运算初识

唯快不破的01序列——位运算初识

转眼就是假期的最后一天,陆续也要返程了,祝旅途顺利~

零.序

1.本篇为简单休息篇。

2.已会人群请直接移位到文末点击心形图标~

一.位运算为何物

这个世界上有10种人:懂二进制的和不懂二进制的。

众所周知,计算机的运算使用的就是二进制,它会把十进制的数转化为二进制,然后进行二进制运算,最后再转回十进制展现给我们。而位运算指的是:由于数字在计算机里的储存方式就是二进制01码,我们直接对其进行“与”、“或”、“移位”……等操作直接得到想要结果,因为这种操作基于二进制,所以更“计算机”一些,也就更快一些。

书面语言是这么讲的:移位运算为什么比乘法除法快?

从效率上看,使用移位指令有更高的效率,因为移位指令占2个机器周期,而乘除法指令占4个机器周期。从硬件上看,移位对硬件更容易实现。

可以说,if你(不是最短运行时间誓不AC || 跟普通同学代码一样就浑身难受 || 急不可耐想要了解计算机的内在)那么我想,位运算是你必须get的骚技能。

二.关于二进制,我科普点闲的

第一个成功实现用机器实现简单计算功能的,是法国数学家Pascal(没错,就是数学课经常出现然后硬把*股型曲线叫心形曲线的那个男人),这时还是十进制的机械计算机,还没有村里的大队会计算盘敲得快。

后来大数学家Leibniz(牛逼人儿我都不翻译)花了足足40年时间改进Pascal的计算机,期间他发明了一种转轮,可以很好地解决进位的问题,在随后的三个世纪里,各种机械计算机都要用到这种转轮。

重点来了,除了改进机械计算机,Leibniz还发明了二进制,它成为了今天计算机的基础。然并卵,Leibniz设计的计算器还是十进制的,和二进制无关,而他发明二进制,从某种程度上是为了证实上帝的伟大。关于这一点,他还给康熙大帝写了封信,希望后者皈依基督教……

又后来,一个叫Shannon的年轻人横空出世,虽然他今天以信息论的提出者为大家所熟知,但他还有一大贡献,就是设计能够实现布尔代数,也就是二进制运算的开关逻辑电路,那时他还只是个硕士。Shannon的想法简单地讲,就是所有的加减乘除运算都可以变成布尔的二进制的逻辑运算(至于Boole大佬,二进制逻辑运算是他在19世纪发明的),而那些二进制的逻辑运算,可以通过简单的电路实现。也就是说,Shannon搭起了一座桥梁,沟通了加减乘除运算和简单的电路,也沟通了一个数字电路的时代。

再后来,发生了怎样的潮起潮落,就是你我都知晓而又正在经历的了。

三.回到位运算

不积跬步,无以至千里。这里无意也无法将所有的位操作都展现出来,只做最简单的介绍。以题带讲,拔剑吧。

POJ 3748:位操作(名字暴露了一切)

假设你工作在一个32位的机器上,你需要将某一个外设寄存器的第X位设置成0(最低位为第0位,最高位为第31位),将第Y位开始的连续三位设置成110(从高位到低位的顺序),而其他位保持不变。对给定的寄存器值R,及X,Y,编程计算更改后的寄存器值R。

Input

仅一行,包括R,X,Y,以逗号","分隔,R为16进制表示的32位整数,X,Y在0-31之间且Y>=3,(Y-X)的绝对值>=3,保证两次置位不会重合

Output

更改后的寄存器值R(16进制输出)

Sample Input

12345678,0,3

Sample Output

1234567c

笔者建议读者自己实现一下,代码巨短无比。

前期知识准备:

&:与运算,就是对应的位取交集,1代表有,0代表无,1100 & 0101 =? 答案:0100.即:12&5=4.

|:或运算,类比的,取并集。1100 | 0101 =? 答案:1101.即12 | 5=13.

~:取反,对每一位取反。~1100 = 0011.还记不记得树状数组那里说过一个数n,n+(~n)=-1?显然加完所有位全是1,补码表示中32位1代表的值就是-1.

<<:移位运算,这个符号是向左移位(规则饶舌,具体百度),作用就是乘2.比如3<<1,就是从0011左移一位变为0110,即6.同理>>右移就正跟左移反过来,是除以2,3>>1 = 0011>>1 = 0001 = 1.所以我们表达2的n次幂常常写成:1<<n。

AC代码:

#include <cstdio>

int main()
{
    int R, X, Y;
    scanf("%x,%d,%d", &R, &X, &Y);//16进制读入了解一下

    R &= ~(1<<X);//X位置0
    R |= 1<<Y;//Y位置1
    R |= 1<<(Y-1);
    R &= ~(1<<(Y-2));

    printf("%x", R);
}

此处仅解释一下X怎么变的,其余同理。

比如我们现在随便举个R,二进制姑且表示为1001吧,前面的一堆0不写了。现在X=3.1<<X将0000的第X位(位数从0开始)转变为1,其他位为0,即1<<3 = 1000(刚好是十进制的8对吧)。取反一下,得0111.&=这东西和+=是一个道理,1001 & 0111,由于无关位得1还是0取决于R,只有X位是0,怎么与都是0,所以会把R位的数字变成0.R就最终等于0001.

本题中的位运算是很常见的小技巧了,尤其有时候要枚举子集的题目。

也可以用bitset,STL这东西大概就是多用用就记住了:

#include <cstdio>
#include <bitset>

int main()
{
    int R, X, Y;
    scanf("%x,%d,%d", &R, &X, &Y);

    std::bitset<32> bt(R);//32位整数//列举了几个不同的写法
    bt.reset(X);
    bt.set(Y);
    bt[Y-1] = 1;
    bt.set(Y-2, 0);

    printf("%x", bt.to_ulong());//to_ulong()将bt的串转换为unsigned long类型的数字
}

四.结语

END。希望大家多多包涵,多多支持,多提意见,积极讨论~

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-10-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DP专题8 | 骨牌摆放问题 POJ 2411(状态压缩DP)

    给你n*m(1<=n,m<=11)的方格矩阵,要求用1*2的多米诺骨牌去填充,问有多少种填充方法。

    ACM算法日常
  • Leetcode 周赛题解 216

    给你两个字符串数组 word1 和 word2 。如果两个数组表示的字符串相同,返回 true ;否则,返回 false 。

    ACM算法日常
  • 给球上色(线段树+离散化) - HDU 1199

    假定待离散化的序列为a[n],b[n]是序列a[n]的一个副本,则对应以上三步为:

    ACM算法日常
  • 【原创】支持向量机原理(一) 线性支持向量机

    支持向量机(Support Vecor Machine,以下简称SVM)虽然诞生只有短短的二十多年,但是自一诞生便由于它良好的分类性能席卷了机器学习领域,并牢牢...

    lujohn3li
  • xgboost融合模型:大学助学金精准资助预测(有数据)

    你所看到的这份代码,是Data Castle数据挖掘公开赛《助学金精准预测》的冠军作品。本程序以大学生的行为数据以及历史获助学金情况作为训练数据集,对代码内的模...

    机器学习AI算法工程
  • [Oracle ASM全解析] asmcmd管理ASM实例

    bsbforever
  • 三种方式给apt设置代理

    有很多第三方工具可以用,比如proxychains,非常好用,不过今天这不是正题。因为有可能没有代理,上网你都做不到,更别提下载软件了。想一想方法还是告诉你,免...

    俺踏月色而来
  • 面试问到AOP就该这样回答

    相信各位小伙伴在准备面试的时候,AOP都是无法绕过的一个点,经常能看到动态代理、JDK动态代理、CGLIB动态代理这样的字眼。其实动态代理是代理模式的一种。代理...

    不一样的科技宅
  • Ubuntu Apache 配置https证书

    解压出四个文件夹和一个csr文件。 四个文件夹(Apache,IIS,Nginx,Tomcat)分别为用不同服务器框架所用的SSL证书。

    lollipop72
  • SQLServer 触发器

    update触发器 当更新表中某列、多列时触发,自动执行触发器所定义的SQL语句

    授客

扫码关注云+社区

领取腾讯云代金券