Four, (50 points) Consider the natural numbers from 0 to $2^{n}-1$, divide them into two categories $A$ and $B$, where $A$ includes all numbers with an odd number of 1s in their binary representation, and $B$ includes all other numbers. Find $\sum_{x \in A} x^{n}-\sum_{y \in B} y^{n}$.

 untranslated part:
将上面的文本翻译成英文，请保留源文本的换行和格式，直接输出翻译结果。

---

Four, (50 points) Consider the natural numbers from 0 to $2^{n}-1$, divide them into two categories $A$ and $B$, where $A$ includes all numbers with an odd number of 1s in their binary representation, and $B$ includes all other numbers. Find $\sum_{x \in A} x^{n}-\sum_{y \in B} y^{n}$.
Let the set of numbers from $0 \sim 2^{n}-1$ with binary representations containing an odd number of 1s be denoted as $A_{n}$, and the rest as $B_{n}$. Then,
$$
\begin{array}{l}
A_{n+1}=\left(B_{n}+2^{n}\right) \cup A_{n}, \\
B_{n+1}=\left(A_{n}+2^{n}\right) \cup B_{n},
\end{array}
$$

where, $B_{n}+2^{n}=\left\{x+2^{n} \mid x \in B_{n}\right\}$.
Similarly, define $A_{n}+2^{n}$.
Given $\left|A_{1}\right|=\left|B_{1}\right|=1$, we know $\left|A_{n}\right|=\left|B_{n}\right|$.
Define $\sum_{x \in A_{n}} x^{r}-\sum_{y \in B_{n}} y^{r}=S(n, r)$.
It is easy to see that $|A|=|B|$.
$$
\text{Thus, } \begin{aligned}
& S(n, r)=\sum_{x \in A_{n}} x^{r}-\sum_{y \in B_{n}} y^{r} \\
= & \sum_{x \in A_{n-1}} x^{r}+\sum_{y \in B_{n-1}}\left(2^{n}+y\right)^{r}- \\
& \sum_{x \in A_{n-1}}\left(2^{n}+x\right)^{r}-\sum_{y \in B_{n-1}} y^{r} \\
= & \sum_{y \in B_{n-1}} \sum_{i=1}^{r-1} \mathrm{C}_{r}^{i}\left(2^{n-1}\right)^{r-i} y^{i}- \\
& \sum_{x \in A_{n-1}} \sum_{i=1}^{r-1} \mathrm{C}_{r}^{i}\left(2^{n-1}\right)^{r-i} x^{i} \\
= & -\sum_{i=1}^{r-1} \mathrm{C}_{r}^{i}\left(2^{n-1}\right) S(n-1, i) .
\end{aligned}
$$

This indicates that $S(n, r)$ can be expressed as a linear combination of $S(n-1,1)$, $S(n-1,2), \cdots, S(n-1, r-1)$.

Next, we prove that for any $n \in \mathbf{Z}_{+}$, for any $j=1,2, \cdots, n-1$, we have
$$
S(n, j)=0.
$$
(1) When $n=2$, $S(2,1)=0$ holds.
(2) When $n \geqslant 3$, if it holds for $n-1$, then for any $j=1,2, \cdots, n-1$, $S(n, j)$ can be expressed as
$$
S(n-1,1), S(n-1,2), \cdots, S(n-1, j-1)
$$

which are all 0. Thus, $S(n, j)=0$ holds.
For $S(n, n)$,
$$
\begin{array}{l}
=-\sum_{i=1}^{n-1} \mathrm{C}_{n}^{i}\left(2^{n-1}\right) S(n-1, i) \\
=-\mathrm{C}_{n}^{n-1}\left(2^{n-1}\right) S(n-1, n-1) \\
=-n \times 2^{n-1} S(n-1, n-1),
\end{array}
$$

Combining with $S(1,1)=1$, we get
$$
S(n, n)=(-1)^{n-1}(n!) 2^{\frac{n(n-1)}{2}}.
$$