Results 1 to 5 of 5

Math Help - Bit string question

  1. #1
    Member
    Joined
    Oct 2007
    Posts
    159

    Bit string question

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,908
    Thanks
    1759
    Awards
    1
    \begin{array}{rcl}<br />
   {\left| {S \cup E} \right|} &  =  & {\left| S \right| + \left| E \right| - \left| {S \cap E} \right|}  \\<br />
   {} &  =  & {2^7  + 2^7  - 2^6 }  \\ \end{array} <br /> <br />
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2007
    Posts
    159

    Bit string question

    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??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,860
    Thanks
    742
    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\,\_\,\_\,\_\,<br />
\_
    . . The blanks can be filled in 2^4 ways.

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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2007
    Posts
    159

    Bit string question

    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Disprove this set of string.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 11th 2011, 01:02 PM
  2. Question on damping string vibration.
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: February 21st 2010, 04:19 PM
  3. String
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 23rd 2009, 06:04 PM
  4. a loaded string
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: February 22nd 2009, 04:49 AM
  5. binary string probability question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: June 1st 2008, 08:56 PM

Search Tags


/mathhelpforum @mathhelpforum