How many times does the binary digit $1$ appear in numbers $0$ to $255$?

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.

• 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 Apr 21 '19 at 12:26

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$$.

• "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$) ?
– MJ13
Apr 21 '19 at 12:46
• @MJ13: Yes.${}$ Apr 21 '19 at 12:47

HINT

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