复述y总的视频
最后的胜负,只与 a , b 最高的不同位有关。在这个不同位上,谁是 1 谁就赢了。
找到这个最高位。
对于所有数,这个最高位要么是1,要么是0。
所以所有的Xi都可以简化为1和0。
并且因为最后a,b在这位不一样,所以必定有奇数个1。
想要赢得比赛,就要拿到最后一个1。
原因是:
1. 0异或不改变结果,0与0异或还是0,0与1异或还是1。
2. 总共有奇数个1,去掉最后一个一定是偶数个,所以此时a b俩数最高位一定同时为1或0。
3. 想要赢得比赛,就要拿到最后一个1,将自己异或为1或将对方异或为0。
假设1的个数为x,0的个数为y。
x = 1时,alice可以直接拿到最后一个1,alice赢。
x > 1时:
1. y 为偶数,alice只要先拿第一个1,之后无论bob拿什么,alice就拿什么,照此发展,alice必然能拿到最后一个1。
2. y 为奇数,无论alice先拿什么,bob只要和alice拿相反的,一轮结束后 x 和 y 都为偶数。之后只要alice拿什么,bob就拿什么。照此发展,bob能拿到最后一个1。