Like if we have to find the number of ways can be represented in bits up to 4 places. We use $2^4$, but why do we use this method?
Asked
Active
Viewed 123 times
1
-
In each spot you can have $2$ characters, $0, 1$. For a binary code of length 1 there are $2^1$ possible ways of ordering the digits. For a code of length $2$, there are $2$ options for the first character, and $2$ for the second, so $2 \times 2 = 4 = 2^2$ etc... – Jan 08 '18 at 14:51
5 Answers
0
A bit has values $1$ or $0$, so $2$ values. You can prove by induction. Suppose that you have $k$ bits and you have $2^k$ ways and you add one more bit. Then you will have that initial $2^k$ ways for every value of the new bit, so $2*2^k=2^{k+1}$
razvanelda
- 1,697
- 8
- 19
0
Hint:
Note that in a binary sequence of length $n$ because it is binary we have the option of choosing either a $0$ or a $1$ to fit each of those $n$ places.
What are the number of sequences, then?
0
The literal meaning of the positional numeral system is that digit in the $n$th place (counting from zero) represents $r^n$, where $r$ is the radix or base. For example, in decimal, $1000 = 10^3$ because there are $3$ zeros. There are one thousand numbers below $1000$, counting zero.
Similarly in binary, there are $2^n$ numbers representable with $n$ bits.
ziggurism
- 16,756
0
Because for each bit you have 2 different simbols.
Then if $n$ denotes the number of bits, this means that we have to make a choice between $1$ or $0$ for $n$ times is: $$\underbrace{2\cdot2\cdot2\cdot\dots\cdot2}_{n\text{-times}}=2^n$$ This happens because every choice is independent from the others.
If you want you can prove it easily by induction.
0
To visualize the method, I would use a binary tree : for each digit you have two choices $0$ and $1$ or left and right in the tree. At the end you have $2^n$ possible ways to get to the last line of the tree.
stity
- 3,500