---

Problem 878

---

XOR-Equation B

We use $x\oplus y$ for the bitwise XOR of $x$ and $y$.

Define the XOR-product of $x$ and $y$, denoted by $x\otimes y$, similar to a long multiplication in base $2$, except that the intermediate results are XORed instead of the usual integer addition.

For example, $7\otimes 3=9$, or in base $2$, ${111}_2\otimes {11}_2={1001}_2$:
$$\begin{array}{r}\phantom{\otimes 111}{111}_2\\ \otimes \phantom{1111}{11}_2\\ \phantom{\otimes 111}{111}_2\\ \oplus \phantom{11}{111}_2\phantom{9}\\ \phantom{\otimes 11}{1001}_2\end{array}$$
We consider the equation:
$$(a\otimes a)\oplus (2\otimes a\otimes b)\oplus (b\otimes b)=k$$
For example, $(a,b)=(3,6)$ is a solution to this equation for $k=5$.

Let $G(N,m)$ be the number of solutions to those equations with $k\le m$ and $0\le a\le b\le N$.

You are given $G(1000,100)=398$.

Find $G({10}^{17},1000000).$

---

异或等式（二）

用$x\oplus y$表示$x$和$y$按位异或的结果。

考虑$x$和$y$的$2$进制长乘法，但将中间结果的相加替换为按位异或，定义其结果为$x$和$y$的异或积，并记作$x\otimes y$。

例如，$7\otimes 3=9$，或在$2$进制下，${111}_2\otimes {11}_2={1001}_2$：
$$\begin{array}{r}\phantom{\otimes 111}{111}_2\\ \otimes \phantom{1111}{11}_2\\ \phantom{\otimes 111}{111}_2\\ \oplus \phantom{11}{111}_2\phantom{9}\\ \phantom{\otimes 11}{1001}_2\end{array}$$
考虑等式：
$$(a\otimes a)\oplus (2\otimes a\otimes b)\oplus (b\otimes b)=k$$
例如，$(a,b)=(3,6)$是上式取$k=5$时的一个解。

若上式取遍所有$k\le m$，考虑其所有满足$0\le a\le b\le N$的解，记$G(N,m)$为所有这些解的数目。

已知$G(1000,100)=398$。

求$G({10}^{17},1000000)$。

---