# 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. Any help is appreciated.Thanks in advance!

• 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 at 12:26

## 2 Answers

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

HINT

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