0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for the simple explanation! $\endgroup$ – Kot May 6 '14 at 6:23
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$

| cite | improve this answer | |
$\endgroup$
0
$\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.

| cite | improve this answer | |
$\endgroup$
0
$\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.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.

| cite | improve this answer | |
$\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.