Number of bit strings of length 8 that do not contain "$100$"? I am thinking the total number of possible strings is $2^8$ and the number of strings with $100$ at the beginning would be $2^8 - 2^3 = 2^5$. Now "$100$" can shift across the string $5$ times going to the right. Is the answer then $2^8 - 2^5 \times 5$? 

As discussed in the comments, the straight forward approach as proposed in the question won't work because it multiply counts the bad strings in which $100$ appears more than once (indeed, it counts bad strings once for each appearance of $100$). 
For short strings (like length $8$) a more careful count via the principle of Inclusion/Exclusion isn't impossible but it's not exactly easy and, as the length increases, this method gets harder and harder.  I think it's easier to attack the problem recursively.  Toward that end, define some sub-types of the "good" strings of length $n$.  Specifically, let $A_n$ denote those good strings that end in $1$ and let $B_n$ denote those that end in $10$.  Note that the total $T_n$ is then given by $$T_n=A_n+B_n+1$$ where the $1$ comes from the good string $0^n$ which ends in neither $1$ nor $10$.  
Recursive, we note that $$A_n=A_{n-1}+B_{n-1}+1=T_{n-1}$$  since you get a good string of length $n$ by appending a $1$ to any good string of length $n-1$.  Similarly $$B_n=A_{n-1}=T_{n-2}$$  Thus $$T_n=T_{n-1}+T_{n-2}+1$$
It is easy to see that $A_1=1$, $A_2=2$, $B_1=0$, $B_2=1$ whence $$\{T_n\}=\{2,4,7,12,20,33,54,88,\cdots\}$$
Consistency Check:  Let's count $T_4,\;T_5,\;T_6$ directly.  There are $16$ strings of length $4$ and the bad ones are $x100$ and $100x$, thus there are $4$ bad strings so $T_4=16-4=12$ as desired.  Similarly the bad strings of length $5$ are $100xx$,  $x100x$, $xx100$ so $T_5=32-12=20$ as desired.  To count the bad strings of length $6$ we have to be a little careful...the patterns are $100xxx$, $x100xx$, $xx100x$, $xxx100$ but we have to add back $1$ for the double counted string $100100$.  Thus $T_6=64-8\times 4+1=33$ as desired.
Induction shows that, in fact, $T_n=F_{n+3}-1$ where $F_i$ denotes the Fibonacci numbers $\{F_i\}_{i=1}^{\infty}=\{1,1,2,3,5,8,13,21,\cdots\}$
