异或运算
异或运算定义:异或运算方法是一个二进制逻辑运算,设其运算符合为^,a,b为二进制数,则a,b的异或为a^b。
其运算满足如下:1^1=0,0^0=0,1^0=1,0^1=1,即 相同的为0,不相同为1。
a、b按低位到高位进行1位的二进制运算(高位没有则补0)即得a^b的值。
public class Xor { public static void main(String[] args) { System.out.println(Integer.toBinaryString(34)); System.out.println(Integer.toBinaryString(23)); System.out.println(Integer.toBinaryString(34^23)); } }
输出:
100010 10111 110101
异或运算的一些基本性质:
1、交换律:a^b=b^a (根据定义显然可得)
2、结合律:a^b^c=a^(b^c) (根据定义显然可得)
3、对于任何数a,都有a^a=0,a^0=a(根据定义显然可得)
3、自反性: a^b^b=a (a^b^b=a^(b^b)=a^0=a)
尼姆博奕(Nim Game):有三堆各若干个物品(显然每堆的物品数大于0),两人轮流从某一堆取任意多的物品,每次最少取一个,不设上限,最后取光者获胜。
(一般谈论这个博弈时,都会先谈到 巴什博奕、威佐夫博弈)
设(a,b,c)为三堆石子的个数(a>=0;b>=0;c>=0),先手为 甲;后手为乙。
必败局势,一般称为奇异局势,显然(0,0,0)是一个奇异局势(因为谁面对这种局势,都无法做到游戏给出的条件:每次最少取一个)
讨论局势是必败还是必胜,都是相对于首先面对此局势者来说。因此站在甲的角度来讨论。甲面对(0,0,0)必输。
当甲面对(a,a,0),甲每次拿x,乙随后也跟着拿x,因此甲面对的局势始终是(a-x,a-x,0)。因此转化为甲最终都会面对(0,0,0),因此甲必输。
因为游戏是两个人交替进行。由此可得,如果局势(a,b,c)是必胜局势,那么甲就有策略,使得拿走某堆中的x个物品后,一般地设为(a-x,b,c)=(a',b,c)。此时
(a',b,c)就是一个必败的局面。反之,必败的局面可以变为必胜的局面。由此,我们寻找一个函数F,当
F(a,b,c)=1时,称(a,b,c)为必胜局面,F(a,b,c)=0时,称(a,b,c)为必败局面(奇异局势)。
更一般地,考虑N>=2堆物品的情况。每堆数量为(a1,a2,...,aN) (1,2,..,N一般在数学中用下标表示)
定理:(a1,a2,...,aN)为奇异局势当且仅当a1^a2^...^aN=0
证明:(a1,a2,...,aN)=(0,0,...,0)时显然成立。
当(a1,a2,...,aN)不为(0,0,...,0)时,若a1^a2^...^aN=k<>0,显然k的最高位为1。
则一定存在一个ai(1<=i<=N),它在k的最高位的值为1。(若a1,a2,...,aN在k的最高位处都为0,那么异或运算规则,不可能得到k的最高位为1)
因此,ai^k<ai(因为最高位变为0了)
设ai'=ai^k,则a1^a2^...^ai'^...^aN=a1^a2^...^ai^...^aN^k (代入ai'=ai^k,并由异或的交换律得到)
=k^k=0
因此当a1^a2^...ai^...^aN=k<>0时,存在移动ai->ai' (即移动ai-ai'>0)使得a1^a2^...ai^...^aN=0
若a1^a2^...ai^...^aN=0,则不存在合法移动,使得a1^a2^...ai‘^...^aN=0。
因为若a1^a2^...ai^...^aN=a1^a2^...ai’^...^aN=0,则两边同时异或a1,可得a2^...ai^...^aN=a2^...ai’^...^aN,
继续两边异或a3...aN(除了共有的ai,ai'),由此可推出ai=ai'。显然这不是合法的移动。
由以上证明得出
1) a1^a2^...ai^...^aN=k<>0,一定存在一步特定移动使得a1^a2^...ai^...^aN=0;
2) a1^a2^...ai^...^aN=0,不存在一步合法移动使得a1^a2^...ai‘^...^aN再次为0,
即当 a1^a2^...ai^...^aN=0时,任意移动一步后都会变为 a1^a2^...ai’^...^aN<>0。
由1)、2)可得
3)当a1^a2^...ai^...^aN=0时,下一步必然为a1^a2^...ai’^...^aN<>0,再下一步可以变为a1^a2^...ai’’^...^aN=0。
必要性:由(a1,a2,...,aN)为奇异局势(必败局势),考虑甲先乙后。
假设a1^a2^...ai^...^aN<>0,那么甲通过移动,可使a1^a2^...ai‘^...^aN=0。如此一直下去,每次乙都只能面对a1^a2^...ai^...^aN=0的局势。
由于游戏的结束点必然为(0,0,...,0),因此乙最终将面对(0,0,...,0)。在乙面对(0,0,...,0)的上一步,设为(b1,...,bN),此时b1^...^bN<>0。
但乙最终先面对了(0,0,...,0),显然是甲胜,这与(a1,a2,...,aN)为奇异局势(必败局势,甲必败)矛盾。
因此必有a1^a2^...ai^...^aN=0。
充分性:由a1^a2^...^aN=0,由3)乙始终有办法让甲面对的局势始终是x1^x2^...^xN=0。因此甲最终面对的必然是(0,0,...,0)的局势,
而(0,0,...,0)就是个奇异局势。
证毕。
相关推荐
可进行十六进制字符串按位异或运算,就是输入十六进制数,每个十六进制数间输入空格,然后点输出即可得到结果
异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或运算 进行加密 delphi编写异或...
加密解密 (利用异或运算) 进行异或加密解密运算
用于计算十六进制的异或运算,内含源文件以及执行文件
异或运算,传入两个数据进行异或运算。得到相应的数据
最新单片机仿真 用P0口显示按位异或运算结果最新单片机仿真 用P0口显示按位异或运算结果最新单片机仿真 用P0口显示按位异或运算结果最新单片机仿真 用P0口显示按位异或运算结果最新单片机仿真 用P0口显示按位异或...
异或运算在卡诺图中的表示方法,将他们紧密的联系在一起。
基于BP网络的异或运算多阈值神经元的实现 基于BP网络的异或运算多阈值神经元的实现 毕业论文专用
异或运算加密(Delphi) 一个Delphi写的异或加密解密工具
异或运算的真值表,例子展示异或运算 该资源仅供学习!!!
282-用P0口显示按位异或运算结果(51单片机C语言实例Proteus仿真和代码)282-用P0口显示按位异或运算结果(51单片机C语言实例Proteus仿真和代码)282-用P0口显示按位异或运算结果(51单片机C语言实例Proteus仿真和代码)...
基于Keil+51单片机用P0口显示按位异或运算结果.rar(源码+仿真)基于Keil+51单片机用P0口显示按位异或运算结果.rar(源码+仿真)基于Keil+51单片机用P0口显示按位异或运算结果.rar(源码+仿真)基于Keil+51单片机用P...
什么是异或运算,异或运算的作用参考.doc
奇偶校验的基本运算是异或运算。实现这一功能的电路称为奇校验电路;输出端加一个非门,则可得到偶校验电路。通常合二为一,称为奇偶校验电路。
异或运算加密,开发环境vs2013,仅支持整型数据加密,能够实现加密和解密。
异或校验工具。十六进制异或值计算。。。。。。。。。。
神经网络-实现异或运算功能(NeuralNetworkForXor) VB6源码 算法:BP算法,动量,delta-bar-delta(需改动注释) 架构: 输入层PEs:2 输出层PEs:1 中间层PEs可自定义。 MSE(Mean Square Error)输出至txt供分析参考...
图像除法运算图像(位与,位异或,位移运算)
题目描述:给你n个正整数,你要找出哪两个数按位异或运算后的结果是最大的。 输入:输入一个整数n(2<=n<=100000),然后就是n个109以内的正整数。 输出:输出最大的按位异或运算结果。 样例输入: 4 1 3...
最简单的进行两图像的加减和异或,同或,运算。