简单的容斥原理

大家一定听过这样一类问题：

班级里有 a 个同学喜欢语文，在这 a 个同学里，喜欢数学的有 b 个人，那么班里有多少个同学只喜欢语文呢？

答案呼之欲出：那就是 a - b。

知道这个原理后，我们再来看这道题目：求区间 [a，b] 内有多少个偶数，其中题目规定 1 ≤ a ≤ b ≤ 1000000000。

换言之，本题是否可以转化为：计算区间 [1，b] 的偶数数量与区间 [1，a - 1] 的偶数数量之差？

进一步把该问题代码化：另 f(x) = 区间 [1，x] 的偶数数量，则本题答案为 f(b) - f(a - 1)。

到现在，我们只需要求从 1 到 x 中，有多少偶数就可以了。

那我们又知道，偶数都是 2 的倍数，也就是连续两个整数中，一定有一个是偶数。

所以我们只需要看 x 中有多少个 2，就可以知道 x 中有多少个偶数了，即 f(x) = x / 2。