一天一算法题，神奇的位运算（位运算 算法）

面试中算法题为什么那么重要？现在很多大公司都要求现场写代码，现场写代码总不能让你写个cache怎么调优，应用如何更加高效的部署吧。所以很多公司面试都会选择一些较为简单的算法题，一方面是考察你的算法基础，更重要地是看你分析问题的能力。

大家都知道计算机的基础就是二进制，计算机运算底层就是二进制运算，位运算左右一个基础的运算，在程序设计中被大量地使用，我们几天来讲一讲一个相关的题目。

这个题目是MS公司的在线笔试题目：

给你2个数，0 < l <= r < 100, 000, 000,求l xor (l + 1) xor (l + 2) ... xor (r)

这个题目，可能很多人都会觉得不难，不就是for一遍，然后在输出结果么？这当然是一种解决方法，然而这个方法的效率很低，算法复杂度为O(n)，我们可能需要找到更优的解决方案。

干货1：

解决连续区间的运算问题，我们有一把金钥匙，我们看看能否将f(l, r)转化为 F(R) 与 F(L - 1)的关系。在这个题F(x) = 1 xor 2 xor 3 .. xor x，根据xor的原则，两段(0, L -1)抵消后，结果即为f(l,r)。

思考：

有了上面的基础，我们再来思考怎么求F(x).F(x) = 1 xor 2 xor 3 .. xor x， 这个问题可以转化为：有哪些位，上面有奇数个1.我们先把一个二进制表弄出来，如下：

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

我们注意到，其实每一位上，其实都有一个循环，像第0位，总是（01010101），第2位，总是（0000111100001111），每个都有一个循环节（1 << (i + 1)），并且循环前面都是0，后面都是1，除了第0位，其实对于每一位，我们只要取出最后一个循环节，判断有多少个1即可。第0位我们需要做特殊判断，因为一个循环里面只有1个1。

我们通过代码来说明下上面那个问题，代码是JAVA的。

干货二：

凡是xor问题，一般我们都优先考虑奇偶性

总结：

这个题目，思路还是比较常见，但需要特别小心的就是第0位这种边界情况了，一般人都栽在这里。最后欢迎大家关注我的头条号，定期推送面试相关还有码农码禽码畜感兴趣的东西。当然，如果大家有什么看不懂的，例如优先队列。。。或者想沙茶敏整理哪一方面的面试题目，可以在评论中说出来。