Assuming a random byte has all its bits 0 or 1 with probability $\frac{1}{2}$, independent of each other, the answer to the probability seems to be pretty simple.
The probability that the first x bits of such a number will be zero (or whatever) is $\frac{1}{2^x}$.
About your second question: what is the average number of guesses to find such a number. Actually it's a more general question: what is the number of guesses to find something probability of which is $\tilde{p}$.
Le't calculate this.
$ \langle N \rangle = 1 \cdot \tilde{p} + 2 \cdot (1-\tilde{p}) \cdot \tilde{p} + 3 \cdot (1-\tilde{p})^2 \cdot \tilde{p} + \ldots $
Means you need 1 guess with probability $\tilde{p}$. The probability it doesn't happen on the first guess is $1-\tilde{p}$, hence you need 2 guesses with probability $2 \cdot (1-\tilde{p}) \cdot \tilde{p}$. And so on.
We'll use the following known fact:
$ 1 + (1-\tilde{p}) + (1-\tilde{p})^2 + (1-\tilde{p})^3 + \ldots = \frac{1}{\tilde{p}} $
$ \begin{eqnarray} \langle N \rangle &=& 1 \cdot \tilde{p} + 2 \cdot (1-\tilde{p}) \cdot \tilde{p} + 3 \cdot (1-\tilde{p})^2 \cdot \tilde{p} + \ldots = \\ &=& \tilde{p} \cdot \left[ 1 + 2 \cdot (1-\tilde{p}) + 3 \cdot (1-\tilde{p})^2 + \ldots \right] = \\ &=& \tilde{p} \cdot \left[ 1 + (1-\tilde{p}) + (1-\tilde{p})^2 + \ldots + (1-\tilde{p}) + (1-\tilde{p})^2 + ... + (1-\tilde{p})^2 + (1-\tilde{p})^3 \ldots \right] = \\ &=& \tilde{p} \cdot \left[ \frac{1}{\tilde{p}} + (1-\tilde{p}) \cdot \frac{1}{\tilde{p}} + (1-\tilde{p})^2 \cdot \frac{1}{\tilde{p}} + \ldots \right] = \\ &=& 1 + (1-\tilde{p}) + (1-\tilde{p})^2 + ... = \frac{1}{\tilde{p}} \end{eqnarray} $
$ \langle N \rangle = \frac{1}{\tilde{p}} $
Hence the answer to your question is $\langle N \rangle = 2^x$.