Finding the total number of 8 bit strings.

I was wondering how I could find the total number of 8 bit strings. I know that a bit string can contain either a 0 or 1 and there are 8 digits. I think I have found a general solution to these types of problems but I do not understand why it works. The answer was $2^8$ which was a total of $256$ strings.

A similar problem with 16 bit strings had a total of $2^{16}$ strings. I do not understand why this is the case. Could someone please explain?

Well you have two choices for each of your $8$ digits. So you end up getting $2$ choices for the first digit times $2$ choices for the second digit etc. Giving you your result of $2^8$.

If for example we are looking at $3$ bit strings we have $2^3 = 8$ possible strings. Let's write them out: $000, 001, 010,100, 011, 101, 110, 111$.

In general for an n-bit string we get $2^n$ possible strings.

• Thank you for the simple explanation! – Kot May 6 '14 at 6:23

Let's start with just 3 bits. For your first bit, it can be either a 1 or a 0: 1xx, 0xx

Now for both of those, each second spot can be a zero or one, so you get 11x, 10x, 01x, 00x

And finally the last spot can be either a 0 or 1 as well: 000, 001, 010, 011, 100, 101, 110, 111

So what you get is the number of choices per spot: 2 choices in the first, * 2 choices in the second * 2 choices in the third. This gives you $2^3 = 8$

This carries for as many choices and spots as you like, you could do, say, the number of possible variations in a 3 letter string. 26 characters possible, 3 spots, so 26 choices of 26 choices of 26 choices ... $26*26*26 = 26^3$

If you add more spots, you just keep raising the power.

What if not every spot has the same number of choices? Well ... say you have a 4 character string where two characters are letters and two are numbers:

$26*26*10*10 = 26^2*10^2$

Think of this as a Cartesian product. Consider $B = \{0, 1\}$. Your string has $8$ digits, so $\omega \in B^{8}$, where $B^{8} = \prod_{i=1}^{8} B$. And so $\omega = (b_{1}, b_{2}, ..., b_{8})$, with each $b_{i} \in B$. By rule of product (as you would expect since we're taking a Cartesian product), we multiply the number of possibilities for each $b_{i}$, since each $b_{i}, b_{j}$ for $i \neq j$ are independent. That is, the choice for $b_{1}$ does not affect the choice for any other $b_{j}$.

And so there are $2^{8}$ such binary strings.

For the sake of an example, consider all 3-bit strings. The easiest way to internalize this is by thinking of it as a tree diagram.

At every node, we make a choice. We either add $1$ to the existing string and go left, or add $0$ and go right. So you can even think of every level as an empty dash like so _ _ _

So, for every dash, we have two choices, either a $0$ or a $1$. You can extend this reasoning for more dashes or an arbitrary $n$ bit string. As an extended exercise (after you intuitively grasp this), you could think about permutations in the same way (except that at every node, your choices reduce by $1$).

To conclude, for all $n$ bit strings over an alphabet $A = \{1,2 \dots m\}$, we have $m^n$ strings.