求[1,n]所有数的异或和
如果加以打表，我们会发现其异或和有一定的规律
我们设f(x,y)表示区间[x,y]的异或和
那么有
对于k>=1
中，最高位的1出现了次，异或和为0，所以最高位可以去掉
所以
由此，对于所有，有
所以，对于，设其最高位为
那么
在中，最高位出现的次数取决与n的奇偶
1、若n为奇数，那么最高位出现了次为偶数，可以去掉
，可以发现与n具有相同的奇偶性，可以利用同样的推导去掉
最后的就取决于<4的部分，即mod 4后的异或和
那么我们有：
如果n为奇数
若，
若，
2、若n为偶数，那么最高位出现了次为奇数，一定可以保留
同样的，，可以发现与n具有相同的奇偶性，可以利用同样的推导去掉
最后的后两位就取决于<4的部分
那么我们有：
如果n为偶数
若，
若，
这样，我们就get了一个求连续数字异或和的方法
若，
若，
若，
若，
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/5395.html