按位异或及其在求解游戏策略问题中的应用
李学武
（原载:《计算机科学》 2001.10）
摘要 本文给出了关于按位异或运算的若干性质，在此基础上给出了该运算的两个较为重要的结果（定理1、定理2），并给出了它们在涉及到平衡态的游戏策略问题中的具体应用. 有关结果未曾在其它资料中找到.
关键词 异或；按位异或；游戏策略；平衡态
中图分类号
在下文中，N*均表示非负十进制数的集合
1 按位异或的若干性质
定义1：（a⊙b） 设a,b∈{0,1}, 两个一位二进制数a ，b的异或a⊙b的真值表如下：
|
a |
b |
a⊙b |
|
1 |
1 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
0 |
0 |
0 |
定义2：(x xor y) x,y∈N*, 两个非负十进制数 x,y的按位异或 x xor y是对相应的二进制数按位进行⊙运算，其结果仍转换为十进制数. 如果相应的二进制位数不等，较小的数前面的空白按零处理.
例：10 xor 3 的值是9.
一些高级计算机语言，如C，(扩展)PASCAL等都支持对十进制整数的xor运算(参看[1]).
⊙运算的性质：
性质1: (交换律）若a,b∈{0,1}，则a⊙b= b⊙a.
性质2:(结合律) 若a,b,c∈{0,1}，则(a⊙b) ⊙c=a⊙(b⊙c).
性质1、2 容易利用定义1中的真值表验证.
xor运算的性质
在下文中，x,y,z∈N*, x1,x2,…,xn∈N*.
性质3: x xor 0=x.
性质4: x xor y=0 的充分必要条件是x=y.
利用定义2容易证明性质3、4.
性质5：（交换律） x
xor y = y xoy x
证明：设x=(bt…b1b0)2,bi∈{0,1}, i=0,1,…,t,
bt=1; y=(cr…c1c0)2, ci∈{0,1},
i=0,1,…,r, cr=1.
不妨设t≥r, 可在cr 之前补r-t个零，即ct
=…=cr+1=0, 由性质1， bi⊙ci=ci⊙bi,
i=1,…,t,
所以性质5成立.
性质6:（结合律） (x
xor y)xor z=x xor(y xor z)
证明与性质5类似（利用性质2）
性质7:（增广律）若x=y, 则x xor z=y xor z.
性质7可利用定义1、2直接导出.
性质8：若x<2t, 则x xor 2t=x+2t
性质9：设x=(bt…b1b0)2,
bi∈{0,1}, i=0,1,…,t, bt=1; 则x xor 2t=x-2t
性质8、9 可利用定义1、2直接导出.
性质10:
若x<2t, 且y<2t,
则(x xor y)+2t=x xor (y+2t).
由已知及定义，易知x xor y<2t， 由性质8， (x xor y)+2t
= x xor y xor 2t =
x xor (y xor 2t) = x xor (y +2t), 故性质10成立.
性质11:
x与偶数个y 的异或仍为x ,即：x xor y xor y xor… xor y=x（共偶数个y）.
这是性质3、4的直接推论.
定义3：（T） 设x1,x2,…,xn∈N*, 则：T=x1 xor x2 xor…xor xn.
定义4：（Ti）设x1,x2,…,xn∈N*,
则Ti=T xor xi,
i=1,2,…,n.
由性质3、4， Ti实质上就是对{ x1,x2,…,xi-1,xi+1，…,xn}中的n-1个数求异或.
定义5：（取数操作） 在n个非负整数序列x1,x2,…,xn中，选取一个xi及正整数b, 满足xi≥b＞0，再用yi=xi-b取代序列中的xi，称为对序列x1,x2,…，xn的一个取数操作.
定理1：给定N*中的序列x1,x2,…，xn（n≥2），若T≠0，必存在一个取数操作，使yi取代xi后，T ’=x1
xor…xi-1 xor yi xor xi+1 xor …xn=0.
证明：取Ti=T xor xi , 如果存在某个xi>Ti
令b=xi-Ti>0, yi=xi-b=Ti. 由性质3、4,知，用yi代替序列x1…xn中的xi,
即T’=(T
xor xi )xor yi = Ti xor Ti =0.
下面证明必存在某个i ∈{1,2,…,n}, 使xi>Ti .
设序列x1…xn 对应二进制数序列中，最大数的最高非零位为t+1位，最高位的值对应于2t，设这样的数有r个(n≥r≥1)，记相应的集合为A*,分两种情况讨论:
⑴ r是奇数. 不妨设x1∈A*，即 x1≥2t . A*中还有偶数个具有t+1位的数，其中任何两个数的异或均<2t，利用性质3、4可知
T1=T xor x1<2t, ∴x1>T1,结论正确.
⑵ r是偶数.不妨设 x1…xr ∈A*，其余xj均小于2t，在T中添加r(偶数)个2t：T=x1
xor x2…
xor xr xor …xor xn
=(x1 xor 2t) xor … xor (xr xor
2t) xor …xor
xn (根据性质11)
=y1 xor y2 …xor yr xor xr+1
…
xor xn
根据性质9，yi=xi-2t,i=1,…,r, 序列y1,y2,…yr,xr+1…xn 对应的二进制数序列中的最大数最高非零位为s+1位，显然s<t，设最高位对应于2s的数有p个，若p是奇数，则已;
若是偶数，则重复上述操作，直到某一步，具有相同最高位的数的个数为奇数个为止.我们说这一步必然能达到，否则，若具有相同最高位的数的个数永远为偶数，其结果必导致T=0，与题设矛盾.
将上述操作的最后的结果记为y1…yp，yp+1…yn.由于每次只增加了偶数个2i的异或，由性质11，T的值不变.其中
y1…yp各数对应的二进制数的最高位对应于2t，其余yj均小于2t，且p是奇数.
T=y1 xor …xor
yp xor yp+1 …xor yn .
下面证明x1>T1
易知：x1=y1+2t1+…+2tu，其中，t1>t2>…>tu ,即y1 是由x1依次经过对2t1，…2tu ，的异或得到的（参看性质8、9）.
利用前面⑴的分析，易知y1>T xor y1， 显然 T
xor y1<2ti，i=1，…u; ∴y1+2t1+…+2tu>(T xor y1)+2t1+…+2tu ,左边即为x1，右边多次利用性质10，可得：
（T xor y1）+2t1+…+2tu =T xor
(y1+2t1+…+2tu
) =T xor x1=T1即 x1>T1, 证毕.
例：设(x1,x2,x3,x4)=(10,11,13,15)
T=10 xor 11 xor 13 xor 15
=(10 xor 8)xor(11 xor 8)xor(13 xor 8)xor(15 xor 8) （性质11、5、6）
=2 xor 3 xor 5 xor 7 （性质9）
=2 xor 3 xor (5 xor 4) xor(7 xor 4) （性质11）
=2 xor 3 xor 1 xor 3 （性质9）
=y1 xor y2 xor y3 xor y4 = 3
这时，大于或等于21的yi有3个，为奇数，由定理1的证明过程可以断定x1>T1,x2>T2,x4>T4,
但不能保证x3>T3.对x1取数，得：T1=T xor x1=3
xor 10=9, b=x1-T1=1, y1=T1=9, T’=T xor X1
xor y1=3 xor 10 xor 9=0.
定理2：设T=0，对序列x1…xn 作任一次取数操作，即取xi 及正数b，满足xi≥b＞0，然后用yi=xi-b代替xi
(xi＞yi≥0）后，记T’=x1 xor … xi-1 xor yi
xor xi+1 …xor
xn，则必有T’≠0.
证明：令yi=xi-b, xi≥b＞0, yi≥0，T’=T xor yi
xor xi (即从T中去掉xi,加上yi)
=yi xor xi =yi xor（yi +b）(注意
T=0).如果T’=0，由性质4，必有
yi=xi 从而导致b=0，与b>0矛盾，证毕.
如果将T=0的情形定义为某系统处于平衡态，T≠0的情形定义为处于非平衡态，定理1、定理2表明：当系统处于非平衡态时，至少存在一种取数操作，将其变为平衡态；当系统处于平衡态时，任何一个取数操作都将导致非平衡态.
2 一类游戏策略问题及解法
2.1
(取石子游戏1) 任给N堆石子,堆数N 及每堆石子数由游戏者给出，两人(游戏者与计算机)轮流从任一堆中任取(每次只能取自一堆),计算机先取,取最后一颗石子的一方获胜.
试设计一种方法，使计算机有较多的获胜的机会.
分析：记第i堆石子数为xi ，T=x1 xor x2… xor xr
xor …xor xn，显然，有必胜策略的一方应在取数操作之前面临非平衡态，操作后留给对方平衡态.根据定理1与定理2，如果初始状态时T=0，计算机一方没有必胜策略，可在最多的一堆中取一颗，寄获胜希望于对方的失误.如果初始状态时T≠0，由定理1，必存在某个xi>Ti
，可在第i 堆中取xi-Ti 颗，使对方永远处于T=0的平衡状态，计算机必胜.
C语言程序如下：
#include <stdio.h>
unsigned int a[11], n;
void init1()
{int i;
printf("input n(2--10):"); scanf("%u",&n);
for (i=1;i<=n;i++)
{printf("input No.%d Number of stone:\n",i);
scanf("%d",&a[i]);}
}
void status()
{int i;
printf("Now remainder:\n");
for (i=1;i<=n;i++) printf(" No.%d rem: %u \n",i,a[i]);
}
unsigned int sum1()
{unsigned int s; int i;
for(s=0,i=1;i<=n;i++) s+=a[i];
return s;
}
unsigned int xorall()
{unsigned int s; int i;
for (s=0,i=1;i<=n;i++) s^=a[i];
return s;
}
main()
{unsigned int t; int i,s,e;
init1();
while (sum1())
{if (xorall()==0)
{for (i=1;i<=n;i++)
if(a[i]>0)
{printf("computer take 1 from No.%d \n",i);
a[i]--; break;
}
}
else
for (i=1;i<=n;i++)
{s=a[i]-(xorall()^a[i]) ;
if (s>0)
{printf("computer take %u from No.%d \n",s,i);
a[i]^=xorall();
break;
}
}
if(sum1()==0)
{printf("computer win!"); break;}
status();
while (1)
{printf("Input your selection\n(exp. 1 2 means take 2 from No.1):\n");
scanf("%d %u",&e,&t);
if ((e>=1)&&(e<=n)&&(a[e]>=t))
{a[e]-=t; break;}
else
printf("data error! re-input...\n");
}
if(sum1()==0)
{printf("you win!"); break;}
}
}
2.2
(取石子游戏2) 任给N堆石子,堆数N 及每堆石子数由游戏者给出，两人(游戏者与计算机)轮流从任一堆中任取(每次只能取自一堆),规定每方每次最多取K颗，计算机先取,取最后一颗石子的一方获胜.试设计一种方法，使计算机有较多的获胜的机会.
分析：记第i堆石子数为xi ，令yi=xi mod
(K+1), i=1,…,n, 定义T=y1 xor y2… xor yr
xor …xor yn . .如果初始状态时T=0，则为平衡态，先走的计算机一方没有获胜策略，如果初始状态时T≠0，由定理1，必存在某个yi>Ti
，可在第i 堆中取yi-Ti
颗，使对方处于T=0的平衡状态，在以后的各轮中，对方在第i堆中取r颗，若 xi>k,计算机就在同一堆中取k+1-r颗, 这时yi不变. 若 xi≤k,则重新计算yi及T，按问题2.1的方法选取，这时，计算机有必胜策略. 具体实现细节不再赘述.
对上述算法略做修改，便可解决问题2.1、2.2的对偶问题：取最后一颗石子的一方为失败.
参考文献：
[1]
B.W.Kernighan & D.M.Ritchie, The C Programming Language
2nd,Prentice Hall,1988,
p.48, p.207.
Li Xuewu
(Dept. of Computer Science, Tianjin
Normal University, Tianjin , 300074)
Key
words: exclusive OR ; bitwise exclusive OR; strategy for playing; balance status
作者通讯地址：李学武 （天津师范大学计算机科学系（天津市河西区八里台），邮编300074）