Greatest possible cardinality of a set of numbers less than 1000 such that the sums avoid powers of 2
For any $n\in\mathbb N$, let $h(n)$ mean the distance from $n$ up to the next power of $2$ -- that is, in symbols, $$ h(n) = 2^{\lfloor 1+\log_2 n\rfloor} - n $$ It is easy to see that if $a+b$ is a power of $2$ and $a\le b$, then $a=h(b)$. Therefore, the condition of $T$ is equivalent to saying that $T$ does not contain both $b$ and $h(b)$ for any $b$, or in yet other words $T\cap h(T)=\varnothing$.
Let $S^*$ be $S\setminus h(S)$, the elements of $S$ that are not hit by $h$. These elements are "gratis" to add to $T$ in the sense that if $T_1$ satisfies the condition, then $$ T_2 = \bigl(T_1 \setminus h(S^*)\bigr) \cup S^* $$ will be another qualifying $T$, and in addition $T_2$ that has at least as many elements as $T_1$. Namely, each element of $h(S^*)$ that was in $T_1$ but is removed corresponds to at least one element of $S^*$ that is added.
Therefore, we can assume without loss of generality that a $T$ of maximal size contains $S^*$.
For $S=\{1,2,3,\ldots,1000\}$, we have $S^*=\{513,514,\ldots,1000\}$, so these $488$ elements are certainly in $T$. And $h(S^*)=\{24,25,\ldots,511\}$ so these elements cannot be in our $T$. Neither can $512$, of course, being a power of $2$ itself.
So all we have to do now is to supplement with as many elements of $S_2=\{1,2,3,\ldots,23\}$ as we can. But that's just a smaller instance of the problem we're already solving, so we can proceed recursively:
$$ S_2^* = \{17,18,\ldots,23\} \\ h(S_2^*) = \{9,10,\ldots,15\} \\ S_3 = \{1,2,\ldots,7\} $$ (ignoring $8$ which is a power of $2$) $$ S_3^* = \{5,6,7\} \\ h(S_3^*) = \{1,2,3\} $$ at which point we have exhausted the entire original $S$. Therefore, a $T$ with maximal size is $$ \{5,6,7,17,18,\ldots,22,23,513,514,\ldots,1000\}$$ with $$ 3+7+488 = 498 $$ elements.
This is not the only possible $T$ with $498$ elements, though. For example, $$ \{5,6,7,17,18,\ldots,22,23,24,513,514,\ldots,999\}$$ would also work.
According to the approach described by Henning Makholm if $S=\{1,2,\dots,n\}$ it seems that the maximum size of such set $T(n)$ is related to $[n]_2$ (the binary expansion of $n$). It should be $$|T(n)|=\frac{n-\mbox{number of runs in $[n]_2$}}{2}$$ For $n=1000$ then $[n]_2=1111101000$ and $$|T(1000)|=\frac{1000-4}{2}=498.$$ Is there any connection between Gray code and this problem?
This is not a solution, but some random thought you might find usefull.
If $a + a = 2a$ is a power of two, then a must be a power of two.
For every $a \neq 1$ that is a power of two we can't include both $a+b$ and $a-b$, where $b$ is odd and $a > b$. Thus, a choice is to be made, and it feels like one should include $a-b$ and not $a+b$ since distance between powers of 2 grows but this needs to be proved.
Lastly, any even number a that is not a power of two is fine to include always.