题解

思路

比较 $x\mathbin{\mathrm{xor}}N$ 与 $N$ 时，最高个发生变化的二进制位就是 $x$ 的最高置位。

做法

若该位在 $N$ 中为 1，异或后它从 1 变为 0，结果必然更小；若在 $N$ 中为 0，结果必然更大。因此，合法 $x$ 的最高置位必须也是 $N$ 的置位。

枚举每个置位 $k$。所有最高置位为 $k$ 的正整数恰好构成区间 $[2^k,2^{k+1}-1]$，把它与 $[L,R]$ 的交集长度累加即可。

复杂度

时间复杂度为 $O(\log N)$，额外空间为 $O(1)$。