There is a positive density of odd numbers which are of the form $2^n+p$ (due to Romanoff), and a positive density which are not of this form (due to van der Corput and Erdos, see this paper for a review and some results on the density). So, for some but not almost all odd numbers, we can get to a prime by subtracting a power of two.

I'm curious about a related question: given an odd integer $m$, is there always a prime number with Hamming distance 1 to $m$? For example, $127 = 1111111_2$ is not of the form $2^n+p$, but it has Hamming distance 1 to a prime, since $383 = 101111111_2$ is prime.

A related question, which implies the first: given an odd integer $m$, does the set $\{m+2^n\mid n\in \mathbb{N}\}$ contain infinitely many primes (or at least one for which $2^n>m$, so that this corresponds to flipping a bit in $m$)?