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?
$\endgroup$4 Answers
$\begingroup$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.
$\endgroup$ 1 $\begingroup$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$
$\endgroup$ $\begingroup$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.
$\endgroup$ $\begingroup$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.
$\endgroup$
