给定一个整数 $n$求出$0sim n$之间满足 $x xor 2×x xor 3×x=0$ 的整数 $x$ 有多少个。

首先，我们可以将 $x$ 表示为二进制形式，即 $x = a_0 + a_1 \times 2 + \cdots + a_k \times 2^k$，其中 $a_i\in{0,1}$，$k=\lfloor \log_2 n \rfloor$。然后，我们可以将 $x$，$2\times x$ 和 $3\times x$ 分别表示为：

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

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

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

移项得：

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

化简得：

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

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

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

分别解决 $a_0$，$a_1$，$\cdots$，$a_k$，就可以得到所有满足条件的 $x$。

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

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

求解该方程，得到：

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

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

时间复杂度为 $O(\log n)$