计算满足 x XOR (2x) XOR (3x) = 0 的整数个数

首先，我们可以将 x 表示为二进制形式，即 x = a0 + a1 × 2 + ··· + ak × 2k，其中 ai∈{0,1}，k=⌊log2 n⌋。然后，我们可以将 x，2×x 和 3×x 分别表示为：

$$\begin{aligned}\x &= a_0 + a_1 × 2 + ··· + a_k × 2^k \2×x &= a_0 × 2 + a_1 × 4 + ··· + a_{k-1} × 2^k + a_k × 2^{k+1} \3×x &= (a_0 + a_1) + (a_1 + a_2) × 2 + ··· + (a_{k-1} + a_k) × 2^k + a_k × 2^{k+1}\end{aligned}$$

将这三个式子代入 x xor (2×x) xor (3×x)=0，得到：

$$\begin{aligned}&(a_0 + a_1 × 2 + ··· + a_k × 2^k) xor (a_0 × 2 + a_1 × 4 + ··· + a_{k-1} × 2^k + a_k × 2^{k+1}) xor \&(a_0 + a_1) + (a_1 + a_2) × 2 + ··· + (a_{k-1} + a_k) × 2^k + a_k × 2^{k+1} = 0\end{aligned}$$

移项得：

$$\begin{aligned}&(a_0 + a_1 × 2 + ··· + a_k × 2^k) xor (a_0 × 2 + a_1 × 4 + ··· + a_{k-1} × 2^k + a_k × 2^{k+1}) xor \&(a_0 + a_1) + (a_1 + a_2) × 2 + ··· + (a_{k-1} + a_k) × 2^k + a_k × 2^{k+1} + (a_0 + a_1 × 2 + ··· + a_k × 2^k) = 0\end{aligned}$$

化简得：

$$\begin{aligned}&(a_0 xor 2a_0 xor 3(a_0 + a_1)) + \&(a_1 xor 4a_1 xor 3(a_1 + a_2)) + \&··· + \&(a_{k-1} xor 2^{k-1}a_{k-1} xor 3(a_{k-1} + a_k)) + \&(a_k xor 2^ka_k) = 0\end{aligned}$$

观察上式，我们发现每个 ai 只与 ai-1 和 ai+1 有关。因此，我们可以将上式拆分为 k+1 个独立的子问题，每个子问题只涉及到一个 ai，即：

$$\a_i xor 2^i a_i xor 3(a_i + a_{i+1}) = 0$$

分别解决 a0，a1，···，ak，就可以得到所有满足条件的 x。

对于每个子问题，我们可以将其转化为一个线性方程，即：

$$(2^i + 1) a_i + 3 a_{i+1} = 0$$

求解该方程，得到：

$$\a_i = -\frac{3}{2^i+1} a_{i+1}$$

因此，我们可以从 ak 开始，倒推出所有的 ai。特别地，ak 可以任意取值，因为 ak+1 没有被使用到。最终，我们只需计算 a0 取值的个数，即可得到答案。

时间复杂度为 O(log n)。