0
$\begingroup$

I am trying to find an easy way to calculate the number of times that the digit "$1$" appears in numbers $0-255$ (in the binary system). I consider the answer must be a power of $2$ since $256 = 2^8$ but I don't know how to approach this. Any help is appreciated.Thanks in advance!

$\endgroup$
  • $\begingroup$ Hint: you can find a recursive formula since each $n$ bit number is an $n-1$ bit number with a $0$ or $1$ as a first bit $\endgroup$ – Μάρκος Καραμέρης Apr 21 at 12:26
3
$\begingroup$

By symmetry, each of the eight bits is $1$ half the time (because, for instance, the number of numbers of the form $xxx1xxxx$ is equal to the number of numbers of the form $xxx0xxxx$).

So the total number of $1$'s is $\frac12(8\cdot 256)=1024$.

This is indeed a power of $2$, but only because $8$ is a power of $2$. In the range $0-127$, the total number of $1$'s is $\frac12(7\cdot 128)=448$, which is not a power of $2$.

$\endgroup$
  • $\begingroup$ "Each of the eight bits is $1$ half the time" The reason this happens is because the range $[0,255]$ includes every possible number with $8$ bits (from $00000000$ to $11111111$) ? $\endgroup$ – MJ13 Apr 21 at 12:46
  • 1
    $\begingroup$ @MJ13: Yes.${}$ $\endgroup$ – TonyK Apr 21 at 12:47
2
$\begingroup$

HINT

There are $C(8, k)$ numbers between $0$ and $256$ that contains exactly $k$ number of $1$'s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.