按位异或及其在求解游戏策略问题中的应用

《按位异或及其在求解游戏策略问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、按位异或及其在求解游戏策略问题中的应用按位异或及其在求解游戏策略问题中的应用李学武（原载：《计算机科学》2001.10）摘要木文给出了关于按位异或运算的若干性质，在此基础上给出了该运算的两个较为重要的结果（定理1、定理2）,并给出了它们在涉及到平衡态的游戏策略问题中的具体应用.有关结果未曾在其它资料中找到.关键词异或；按位异或；游戏策略；平衡态中图分类号在下文屮，N*均表示非负十进制数的集合1按位异或的若干性质定义1：（a0b）设a,be{0,1）,两个一位二进制数a,b的异或aOb的真值表如下：aba0b1101010110

2、00定义2：（xxory）x,yWN*，两个非负十进制数x,y的按位异或xxory是对相应的二进制数按位进行。运算，其结果仍转换为十进制数.如果相应的二进制位数不等，较小的数前面的空白按零处理.例:10xor3的值是9.一些高级计算机语言，如C,（扩展）PASCAL等都支持对十进制整数的xor运算（参看[1]）・G）运算的性质:性质1：(交换律)若a,be{0,1},则aOb二bOa.性质2:(结合律)若a,b,ce{0,1},则(aOb)Oc=a0(bOc)•性质1、2容易利用定义1中的真值表验证.xor运算的性质在下文中,

3、x,y,zWN*,xl,x2,…，xnGN*.性质3:xxor0二x.性质4:xxory=0的充分必要条件是x二y.利用定义2容易证明性质3、4.性质5：(交换律)xxory=yxoyx证明：设x=(bt---blb0)2,biE{0,1},i=0,1,•••,t,bt=l;y=(cr---clc0)2,ciC{0,1},i=0,1,…，r,cr=1.不妨设t>r,可在cr之前补r-t个零,即ct=---=cr+l=0,由性质1,biOci=ciObi,i=l,…,t,所以性质5成立.性质6:(结合律)(xxory)xorz=

4、xxor(yxorz)证明与性质5类似(利用性质2)性质7:(增广律)若x二y,则xxorz=yxor乙性质7可利用定义1、2直接导出•性质8：若x<2,则xxor2=x+2性质9：设x=(bt…blb0)2,bi丘{0,1},i=0,1,•••,t,bt=l;则xxor2t=x-2t性质8、9可利用定义1、2直接导出.性质10:若x<2t,且y<2t,则(xxory)+2t二xxor(y+2t)・由已知及定义，易知xxory<2t,由性质8,(xxory)+2t=xxoryxor2t=xxor(yxor2t)二xxor(y+

5、2t),故性质10成立.性质11:x与偶数个y的异或仍为x，即：xxoryxoryxor••-xory=x(共偶数个y)・这是性质3、4的直接推论.定义3：(T)设xl,x2,…，xnWN,则:T=xlxorx2xof-xorxn.定义4：(Ti)设xl,x2,…，xnGN*,则Ti二Txorxi,i二1,2,…，n.定满作由性质3、4,Ti头质上就是对｛xl,x2,…，xiT,xi+1,•••,xn）中的nT个数求异或.义5：（取数操作）在n个非负整数序列xl,x2,…,xn中，选取一个xi及止整数b,足xi2b>0,再用y

6、i=xi-b取代序列中的xi,称为对序列xl,x2,…，xn的一个取数操•定理1：给定N*中的序列xl,x2,…，xn（n±2）,若THO,必存在一个取数操作，使yi取彳弋xi后，T'=xlxor・・・xiTxoryixorxi+1xor…乂呼。.证明:取Ti=Txorxi,如果存在某个xi>Ti令b二xi-Ti〉0,yi=xi-b=Ti.由性质3、4,知,用yi代替序列xl・・・xn中的xi,即T'=（Txorxi）xoryi=TixorTi=0.下面证明必存在某个iF｛1,2,-,n｝，使xi>Ti・设序列xl-xn对应二

7、进制数序列屮，最大数的最高非零位为t+1位，最高位的值对应于2t,设这样的数有r个（n^r^l）,记相应的集合为A*,分两种悄况讨论：（1）r是奇数.不妨设xlWA*,即xl>2t.A*中还有偶数个具有t+1位的数，其中任何两个数的异或均<2t,利用性质3、4可知T1=Txorxl<2t,/.xl>Tl,结论*t正确.（2）r是偶数•不妨设xl…xrWA*,其余xj均小于2t,在T中添加r（偶数）个2t：T=xlxorx2••-xorxrxor---xorxn二（xlxor2t）xor…xor（xrxor2t）xor---xo

8、rxn（根据性质11）二ylxory2•••xoryrxorxr+1…xorxn根据性质9,yi=xi-2t,i=l,•••,r,序列yl,y2,•••yr,xr+b-xn对应的二进制数序列中的最大数最高非零位为s+1位，显然s〈t,设最高位对应于2s的数有p个，若p是奇数，