Bit string question

**Frostking** · April 11th 2008, 08:04 AM

How many 8 bit strings either start with a 1 or end with a one?

How many 8 bit strings either start with 100 or have the fourth bit a 1?
I know that the answer is 2^5 + 2^7 - 2^4 The first term is the number of strings with 100 the second term is the number of strings with 1 as 4th bit but why is 2^4 the number in which both occur??? Is it simply that there are 2^4 ways to choose four positions???? Thank you all for looking and trying to help my old brain think in new ways.

**Plato** · April 11th 2008, 09:15 AM

$\begin{array}{rcl} {\left| {S \cup E} \right|} & = & {\left| S \right| + \left| E \right| - \left| {S \cap E} \right|} \\ {} & = & {2^7 + 2^7 - 2^6 } \\ \end{array} $

**Frostking** · April 12th 2008, 08:55 AM

Plato, thank you for your explanation. I am a bit confused though. If you have to have 100 then are you not just picking the other 5 bits so the first term would be 2^5??

**Soroban** · April 12th 2008, 09:45 AM

Hello, Frostking!

Maybe my baby-talk approach will help your "old brain".
. . (I bet my brain is older than yours.)

How many 8-bit strings either start with a 1 or end with a 1?

If it starts with 1, it is of the form: . $1\,\_\,\_\,\_\,\_\,\_\,\_\,\_$
. . The blanks can be filled in $2^7$ ways.

If it ends with 1, it is of the form: . $\_\,\_\,\_\,\_\,\_\,\_\,\_\,1$
. . The blanks can be filled in $2^7$ ways.

But there are numbers that start and end with 1,
. . and we have counted them twice.
These numbers have the form: . $1\,\_\,\_\,\_\,\_\,\_\,\_\,1$
. . The blanks can be filled in $2^6$ ways.

Therefore, the number is: . $2^7 + 2^7 - 2^6 \;=\;\boxed{192}$

How many 8-bit strings either start with 100 or have the fourth bit a 1?

If it starts with 100, it is of the form: . $100\,\_\,\_\,\_\,\_\,\_$
. . The blanks can be filled in $2^5$ ways.

If the fourth digit is 1, it is of the form: . $\_\,\_\,\_\,1\,\_\,\_\,\_\,\_$
. . The blanks can be filled in $2^7$ ways.

But there are numbers that begin with 100 and whose 4th digit is 1,
. . and we have counted them twice.
These numbers are of the form: . $1001\,\_\,\_\,\_\, \_$
. . The blanks can be filled in $2^4$ ways.

Therefore: . $2^5 + 2^7 - 2^4 \;=\;\boxed{144}$

**Frostking** · April 13th 2008, 07:22 AM

Thank you very much!!! With that explanation I think I can do just about any bit problem that is given to me. I appreciate your being willing to explain it at such a basic level and stating it so clearly. You do have me in age but not by much!! Have a great day!

Thread: Bit string question

LinkBack

Thread Tools

Display