求1到n这n个整数间的异或值 (O(1)算法)
记 f(x y) 为x到y的所有整数的异或值.
2^k 到 2^(k+1) -1 这2^k个数,最高位(+k位)的1个数为2^k,
若 k >= 1,则2^k为偶数,将这2^k个数的最高位(+k位)去掉,异或值不变.
对2^k到n这n+1-2^k个数,最高位(+k位)共有 m = n+1-2^k 个1去除最高位的1
也就是说,最高位1保持不变,由于n - 2^k 与 n同奇偶,递推上面的公式,
本文采用知识共享署名-非商业性使用-相同方式共享 2.5 中国大陆许可协议进行许可,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利.