我们记
为a到b之间所有数的异或（包括a和b）。
那么我们先来考虑
，一共是2^k个数。这2^k个数中，二进制中最高位为1的是第k+1位，且所有2^k个数的最高位均为1。
我们考虑k>=1，则2^k为偶数，最高位异或后为0，把这个数的最高位去掉，并不会影响的值，所以
所以：
即
对于
，设n的最高位1是在第k+1位(k>=2)，
，对于2^k到n一共m=n+1-2^k个数，最高位共有m=n+1-2^k个1。
（1）当n为奇数时，m=n+1-2^k为偶数，根据公式1，可以进一步化为：
由于n-2^k和n都是奇数，递推上面的公式，可以得到
为什么会得到这个公式？相当于把n去掉其最高位，经过多轮递推后，n只剩下两个位，为什么剩下两个位？因为k>=2，所以剩下的两位无法再进行递推。又因为n为奇数，所以n不是1就是3，写成通项公式的话，就是
所以最终有：
（2）当n为偶数时，m=n+1-2^k为奇数，则最高位共有奇数m=n+1-2^k个1，
，最后和2^k相或，是因为最高位有奇数个1。
经过递推，我们可以知道，n二进制表示中，原来是1的位，依然是1，原来为0的位，依然为0，因为每次递推都会把当时最高位1保留下来，因为k>=2，实则相当于把n的前k-2为保留下来。
n的二进制表示为：
n’记为：
，即把n的最后两位清零， 那么上述公式可以化为：
即当n%4=0时，即n=n’，所以
当n%4=2时，即n=n’+2，所以
综上所述：