A story about this problem: It was originally meant to be D3 P3 (basically the hardest problem in the TSTs), but a few days before the test, some of us found an easier solution while trying. Hence the problem had to be demoted to D3 P1. D4 P3 at that time, which was a very hard geo, was shifted to D3 P3 (I think it was more suitable for that position anyway), and we had to use the shortlist for D4 P3. Anyway, I think this is a very cute problem. Here is the solution that we found: For $n\in\mathbb N$, let $d(n)$ denote the number of $1$'s in the binary representation of $n$. Let $P(x,y)$ denote the statement that $f(x)+y$ and $f(y)+x$ have the same number of $1$'s in their binary representation. Claim 1: For any $y,n \in \mathbb{N}$ with $2^n>f(y)$, $f(2^n-f(y))+y$ is a power of two. Proof: $P(2^n-f(y),y)$ gives us that $2^n$ and $f(2^n-f(y))+y$ have the same number of $1$'s, and the former has exactly one $1$, so $f(2^n-f(y))+y$ has exactly one $1$, from which the claim follows. $\blacksquare$ Claim 2: $f(y+2^k)-f(y)$ is a power of two for any $k \geq 0$ and $y \geq 2^k$. Proof: Choose an $n$ such that $n>1000+\log_2(10+|f(y+2^k)-f(y)|)$. By Claim 1, $f(2^n-f(y))=2^t-y >0$ for some $t$ with $t \geq k+1$. Therefore $P(2^n-f(y),y+2^k)$ gives $$d(2^n-f(y)+f(y+2^k))=d(2^t+2^k)=2$$since $t \geq k+1$. If $f(y)=f(y+2^k)$, then LHS is $d(2^n)=1$, contradiction! If $f(y)>f(y+2^k)$, and $f(y)-f(y+2^k)$ has $m<\log_2(10+|f(y+2^k)-f(y)|)$ digits, then $$d(2^n-f(y)+f(y+2^k)) \geq n-m-1 \geq 999>2$$since $2^n-f(y)+f(y+2^k)$ starts with at least $n-m-1$ ones, contradiction! Therefore $f(y+2^k)>f(y)$, and since $n$ is bigger that the number of digits in $f(y+2^k)-f(y)$, there is no carry-over, so $$2=d(2^n-f(y)+f(y+2^k))=1+d(f(y+2^k)-f(y))$$which gives us $f(y+2^k)-f(y)$ is a power of $2$, as required. $\blacksquare$ Claim 2 gives us $f(y+1)-f(y)=2^{t(y)}$ for some $t(y)$, for all $y$. But for $y \geq 2$, $f(y+2)-f(y)$ is also a power of two $\implies$ $2^{t(y)}+2^{t(y+1)}$ is a power of two, which is only possible if $t(y)=t(y+1)$ for all $y \geq 2$. Therefore $f(y+1)-f(y)$ is a constant power of two for all $y \geq 2$, say $2^k$. This gives us $f(y)=2^ky+c$ for some constant $c$, for all $y \geq 2$. Putting this in Claim 1, we get $$2^{k+n}-(2^{2k}-1)y-(2^k-1)c$$is a power of two for any $y \geq 2$ and any sufficiently large $n$. This is only possible if, for all $y \geq 2$, $$(2^{2k}-1)y+(2^k-1)c=0$$$$\iff (2^k-1)((2^k+1)y+c)=0$$which can only hold for all $y \geq 2$ if $2^k=1$, i.e., $f(y)=y+c$ for all $y \geq 2$. But Claim 1 for $y=1$ and large $n$ gives $$2^n-f(1)+1+c$$is a power of two for all sufficiently large $n$, which is only possible if $f(1)=1+c$. Therefore the only solutions are $$\boxed{f(x)=x+c \ \ \forall x \in \mathbb{N}}$$where $c$ is a non-negative integer.

$P(2^n-f(x),x)$ means $x=2^k-f(2^n-f(x))$ for some $k$, for all $x,n$. $P(2^a+2^k-f(x),x)$ means that $f(2^a+2^k-f(x))+x$ is of the form $2^c+2^d$, where $c\neq d$ when $a\neq k$ and $c=d$ when $a=k$. Replacing $x$ in the previous equation with $2^n-f(x)$, $f(2^a+x)+2^n-f(x)$ either has one or two ones in its binary representation. If you make $n$ large, we get that $f(2^a+x)-f(x)$ is a power of two for all $a,x$. In the same manner as the previous post, you can get $f(x)=2^kx+c$ for some $k,c$. $P(x,2^kx)$ means $2^{k+1}x+c$ and $(2^{2k}+1)x+c$ have the same number of $1$'s in their binary representation. If $x$ is a large power of $2$, then the second one will have one more $1$ than the first one unless $k=0$. Thus $k=0$ and $f(x)=x+c$, which works.