本帖禁止刷罐头!!!!!
本帖禁止刷罐头!!!!!
本帖禁止刷罐头!!!!!
重要的事情说三遍!!!!!
简介
这篇文章讲的是异或运算,由于篇幅限制,有可能漏掉一些内容,请各位大佬谅解。
话不多说,正文开始!
异或运算简单介绍
异或是位运算,它的算法如下:
1.将两个运算数均转化为二进制。
2.分析两个二进制数的每一个相同位,如果相同,则结果的这一位是0,否则是1。
3.将这个二进制数转化为十进制,运算结束。
异或运算的符号是^。
我们用9^5这个实例来讲解以上文字内容:
1.9=1001(2)1001_{(2)}1001(2) ,5=0101(2)0101_{(2)}0101(2) ;
2.两数的最高两位不同,记为1,最低两位相同,记为0;
3.最后答案为1100(2)1100_{(2)}1100(2) ,即12。
最后结论:9^5=12
异或的性质1
异或运算满足交换律和结合律。
证明:异或运算也有另一种计算方式:将两个二进制数的相同位相加后模2。
由于加法满足交换律和结合律,同时将所有数模2加起来后模2与直接相加再模2是一样的,因此异或满足交换律和结合律。
异或的性质2
对于任何整数a,0^a=a,a^a=0。
证明:异或有4种运算法则:
1.0^0=0
2.0^1=1
3.1^0=1
4.1^1=0
第一个算式运用了法则1和2(0的二进制每一位都是0),第二个算式运用了法则1和4(相同数的二进制表示每一位都相同)。证明过程作者懒得写
有了这两个性质,我们就可以做出一些题目了,比如A92165.找筷子(提示:输入输出要用scanf和printf)
这里附上标程:
似乎好像是那一题的题解
如果你是来抄题解的,点这里和这里
拓展:异或交换数
想当年,作者在*谷有题做题的时候,发现了一道运用它的题目,所以我感觉有必要讲一下这个玩意。
先贴上代码:
以上代码就是用异或实现交换数的代码。
为什么这段代码是正确的呢?我们分3种情况讨论。
1.两个数的同一位均为1:
第一步后:a=0,b=1
第二步后:a=0,b=1
第三步后:a=1,b=1
2.一个数的一位是1(假设它是a),另一个数的这一位是0:
第一步后:a=1,b=0
第二步后:a=1,b=1
第三步后:a=0,b=1
3.两个数的同一位均为0:
第一步后:a=0,b=0
第二步后:a=0,b=0
第三步后:a=0,b=0
通过分类讨论,我们成功证明了以上代码的正确性。
这个代码在实际编程中并不常用(swap不香吗?),但是我们也要把它记住(因为考试有可能会考到)。
小结
这篇文章介绍的异或知识仅仅是作者目前了解的部分,如果有更简洁的证明,没有讲的知识,证明缺少细节或者语言表示不当的,欢迎在评论区补充。