8
$\begingroup$

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when we want to convert a whole number (200) by 2? Obviously, it works but how ?

Take the following example:

Convert $200_{10}$ to binary:

Solution:

     D > B    | Remainder    
-------------------------------------
200 / 2 = 100 | 0    

100 / 2 = 50  | 0             

50/2 = 25     | 0  

25/2 = 12     | 1

12/2 = 6      | 0 

6/2 = 3       | 0 

3/2 = 1       | 1 

1/2 = 0       | 1  

By taking the remainder from bottom-to-top

$200_{10} = 11001000_2$

Why this method works ? In other words, what's the secret behind the division by $2$ ?

Now converting decimals (e.g. 0.5, 0.25) to binary:

Now Suppose we have a decimal like $0.25$ and we want to convert it to binary, one of the method which I know goes like this:

Multiplying the decimal by 2 repeatedly:

0.25 * 2 = {0}.50 | {0}
0.50 * 2 = {1}.00 | {1} 
0.00 
--------------------------
                   .01
                   0.01  

For more details about the above method: Decimal to binary conversion with fraction

You can see the the two operations are reversed, to convert a whole number to a binary we divide by $2$ and to convert a fraction (decimal) we used multiplication. Add to that the order in which we take the result from bottom-to-top and from top-to-bottom. How that works?

(Why division used to convert whole numbers to binary and why multiplication used to convert decimals (e.g. 0.25) to binary?)

$\endgroup$
  • $\begingroup$ Could you elaborate on what you mean by multiplying and dividing by $2$? What is your method for writing e.g. 200 in binary? $\endgroup$ – James May 2 '15 at 16:39
  • 1
    $\begingroup$ @James see the editing $\endgroup$ – direprobs May 2 '15 at 18:16
  • 3
    $\begingroup$ For a given base $b$, using digits from $0$ to $b-1$ inclusive, each nonnegative integer has a unique representation as a sum of terms of the form a digit times a power of $b$, where the powers of $b$ descend successively from some highest power down to the zero'th power. So the reason is the uniqueness. $\endgroup$ – quasi Oct 27 '17 at 18:12
14
$\begingroup$

Why is binary base-2 but decimal is base 10?

This is quite a trivial question, since those are just the terms we use for those bases. It's like asking "why are humans people?"; it's just a word we use. Binary means base-2 and decimal means base-10. There's nothing complicated there.

Why do we use powers of $2$ for binary numbers?

Base-10 and Carrying

Think about how you represent numbers (integers). It's easy for the first $10$, since we just make a new symbol each time: $0,1,2,3,4,5,6,7,8,9$. But, of course, we don't want to make a new symbol for every new number since it'd get very messy and complicated. So for the number after $9$, we start counting in a new place. So, we put a $1$ (shown in blue) in the place on the left, to get $\color{blue}{1}\text{_}$. Then, in the place on the right, we reset our $9$ to $0$ and start counting all over again (shown in red). Hence, after $9$, we get $\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1},\color{blue}{1}\color{red}{2},\ldots$. The $1$ that we put in the left place is called a carry. Of course, when we get to $19$, we change the $1$ on the left to a $2$ and again, reset the $9$ to a $0$. This may seem obvious, but we need to think about exactly what we're doing.

The whole point of doing this is making it simpler and easier to read numbers. With no loss of clarity, we've managed to represent every integer as a sequence of $10$ symbols. This is the system that we almost always use, and is called base-ten or decimal.

To represent bigger numbers in decimal notation, we'd keep putting a new number on the left every time we can't advance our numbers any further. Hence, $9\mapsto10$, and $99\mapsto100$ and $999\mapsto1000$ and so on. Like I mentioned before, we're carrying the $1$ in each case. What's the common feature among $10,100,100\ldots$? Well, they're all powers of $10$. Think about this, since it's important. We started with $10$ symbols (i.e. $0,1,2,3,\ldots$) but whenever we carry a $1$ (to a new position on the left), we do it at a power of $10$. This isn't a coincidence. This happens because we carry the $1$ every time we've maxed out our count in the other columns, which happens at $9$ and $99$ and so on.

This means that when we write the number $1729$, what we actually mean is $$1\times1000\quad+\quad7\times100\quad+\quad2\times10\quad+\quad9\times1$$

This shows us why base-ten is so fundamentally linked with powers of $10$, because the digits of a number tell you how many $1$'s, $10$'s, $100$'s, etc. there are in it.

Base-2

In base $10$, we started with $10$ symbols. But why? Is there a special reason for choosing $10$? It turns out that no, there is no fundamental, mathematical reason to prefer $10$ symbols to a different number (say $8$ or $12$). Notice that the number of symbols is the base. There are cultural, historical and practical arguments for choosing $10$ but these aren't relevant here. In fact, the Native American Yuki People use base $8$, while the Babylonians used base $12$.

Let's say we wanted to use base $2$ for our counting (i.e. only using $2$ symbols). For simplicity, we use the first $2$ symbols we were using before (i.e. $0$ and $1$). If we were using this system, how would we count? We'd start with $0,1,???$ and then what? Well, we'd do the same thing we did before and put a $1$ to the left of our numbers. Hence $\color{red}{0},\color{red}{1}\mapsto\color{blue}{1}\color{red}{0},\color{blue}{1}\color{red}{1}$.

In fact, just like how we max out our base-$10$ count at $9$ or $99$ or $999\ldots$, etc., we max out our base $2$ count at $1_B$ or $11_B$ or $111\ldots_B$ (the subscript B indicates that these numbers are in base-2). To make this clearer, look at how we count in binary:

$$0,1,10,11,100,101,110,111,1000\ldots$$

Every time we get a number only made of ones, we carry over a $1_B$ to the left. For instance, after $111_B$ we get $1000_B$.

But when do we get $1_B$ or $10_B$ or $100\ldots_B$? Looking at these numbers in decimal form should give a clearer indication: $1,2,4,8,16,\dots$. These are the powers of $2$. Since we've only got $2$ different symbols, we max out our count after $2$ numbers or $2\times2$ numbers, or $2\times2\times2\ldots$.

Hence, base-$2$ is fundamentally related to powers of $2$. When we write the base-$2$ number $1011_B$, we really mean:

$$1\times8\quad+\quad0\times4\quad+\quad1\times2\quad+\quad1\times1$$.

Where $1,2,4,8,\ldots$ are the powers of $2$. In other words, $2^0,2^1,2^2,\ldots$

In general, for any system with $n$ symbols, when you write $31415_{\text{(base $n$)}}$, you mean the following, in base-$10$: $$(3\times n^4)+(1\times n^3)+(4\times n^2)+(1\times n^1)+(5\times n^0)$$

Hopefully this clears up why base $10$ has a sum of powers of $10$ but base $2$ has powers of $2$. It's a natural consequence of using any base.

Why do we count with base-$10$ for most things but with base-$2$ for computers

As I wrote earlier, using base $10$ for representing numbers is heavily influenced by history and society. Most often, the numbers you'll deal with in your life will be between $1$ and $200$. For example, how many years old you are, how many cars are on your street or how many eggs you ate this week. Of course, these numbers are unlikely to be massive. So it makes sense to need a base approximately $10$ since small or large bases aren't practical.

For practical purposes, base-$2$ is too cumbersome since it uses so many numbers (the number $100$ is $1100100_B$ in base-$2$) but base $1000$ is completely unfeasible since you'd need $1000$ different symbols. Can you think of $1000$ symbols that look significantly different? I can't.

Hence, we use a base around $8-16$. Some people have used $8$ before, some $12$ and some $16$. It doesn't really matter too much which one you choose. It's handy for the base to have a lot of divisors, since it lets you write simple expressions for fractions (like how $\frac15=0.2$ in base-$10$). Hence $11$ and $13$ aren't used. It's also handy to have the base divisible by $2$ so that $\frac12$ can have a simple expression. So $7,9,15$ aren't typically used. This leaves us with $8,10,12,14$ and $16$. Base $14$ isn't often used since one of its divisors is $7$, and why should we include $7$ as a divisor but not $3$ or $5$? Nevertheless, $8,10,12$ and $16$ have been widely used as bases. This rule doesn't cover every culture since even base $64$ has been used (though it needed a lot of symbols!). Also, as @ Luís Henrique points out, the mesoamerican Maya civilization used an interesting combination of base-$5$ and base-$20$ in their number system.

Other commenters have pointed out the fact that we have $10$ fingers/toes so it's easy to count base-$10$ numbers with your fingers. But this doesn't have a huge amount of bearing (in written math) since you don't often count with your fingers. As @Luís Henrique points out, this may have been much more important in more primitive societies where numbers could be communicated by hand-signs (instead of with written or spoken words), so it may give a historical basis for using base-$10$. On the other hand, computers use binary (base-$2$) since they represent numbers in electronic states (i.e. a lightbulb being on or off). It makes computers a lot simpler and easier to work with (particularly in the design and manufacture of transistors) for them work in binary. Though there have been computers that use base-$3$ (ternary computers), they are less common.

Hopefully this answers your questions.

$\endgroup$
  • 2
    $\begingroup$ Amazing (long and high-quality) answer! $\endgroup$ – Lwins Oct 27 '17 at 20:14
  • $\begingroup$ @Lwins Thanks, mate :) $\endgroup$ – Jam Oct 27 '17 at 20:19
  • 1
    $\begingroup$ "Other commenters have pointed out the fact that we have 1010 fingers/toes so it's easy to count base-1010 numbers with your fingers. But this doesn't have a huge amount of bearing since you don't often count with your fingers." - We don't now, but it probably was an important thing among hunter-gatherers. Anyway, having 10 fingers makes base 10 intuitive - but it also makes base 6 (and even base 2!) intuitive - one can count up to 35 with fingers in base 6, and up to 1023 in base 2. $\endgroup$ – Luís Henrique Oct 28 '17 at 12:52
  • 1
    $\begingroup$ Mayans used a base 20 system, but only three symbols - 0, 1, and 5: upload.wikimedia.org/wikipedia/commons/thumb/1/1b/Maya.svg/… $\endgroup$ – Luís Henrique Oct 28 '17 at 12:56
  • $\begingroup$ @Luís_Henrique Very interesting points; I've edited my answer to include :) $\endgroup$ – Jam Oct 28 '17 at 15:49
8
$\begingroup$

This all boils down to the concept of positional notation. For example, consider the number $19$ (in base $10$), which in base $2$ becomes $10011$. To understand why, you need to understand what this notation mean: $$ 19_{10} = \color{lime}{1}\color{green}{0}\color{olive}{0}\color{grey}{1}1_2 := 1 \cdot 2^0 + \color{grey}{1} \cdot 2^1 + \color{olive}{0} \cdot 2^2 + \color{green}{0} \cdot 2^3 + \color{lime}{1} \cdot 2^4 $$ So, how can we perform this conversion? Observe that repeatedly applying the distributive property of the product over the sum we have $$ \begin{align} 19_{10} &= 1 + 2 \cdot \color{grey}{1} + 2^2 \cdot \color{olive}{0} + 2^3 \cdot \color{green}{0} + 2^4 \cdot \color{lime}{1} \\ &= 1 + 2 \cdot (\color{grey}{1} + 2 \cdot \color{olive}{0} + 2^2 \cdot \color{green}{0} + 2^3 \cdot \color{lime}{1}) \\ &= 1 + 2 \cdot \big(\color{grey}{1} + 2 \cdot (\color{olive}{0} + 2 \cdot \color{green}{0} + 2^2 \cdot \color{lime}{1})\big) \\ &= 1 + 2 \cdot \Big(\color{grey}{1} + 2 \cdot \big(\color{olive}{0} + 2 \cdot (\color{green}{0} + 2 \cdot \color{lime}{1})\big)\Big) \end{align} $$ then you can see that the remainder $r_0$ of $19$ when divided by $2$ is its first binary digit. Then we can perform division by $2$ with remainder on $(19 - r_0)/2$ to find the next digit, $r_1$, and so on.

The case of fractional numbers is similar, after you observe that $$ 0.abc\dotsc_2 := a \cdot 2^{-1} + b \cdot 2^{-2} + c \cdot 2^{-3} + \dotsb $$


Note that this is not the only possible way to perform this conversion, but it is certainly quite an efficient way. Further, by analogy you can tweak this algorithm to write a number in any integer base $b > 1$, with the integers between $0$ and $b-1$ (included) as digits!


Update: Since this was asked in the comments, here's a quick way of finding the binary digits of a given number's fractional part.

First note that if $f$ is the fractional part, then $0 \leq f < 1$. Furthermore, $0 \leq 2f < 2$, and if you look at the above equation for $0.abc\dotsc_2$ you'll see that the integer part of $2f$ is none other than $a$, the first digit of the binary expansion! If you now take out $a$, you can repeat the process, because the same equation tells us that the integer part of $2(2f-a)$ is $b$. In other words, here's the algorithm:

  1. Let $f$ be given such that $0 \leq f < 1$.
  2. The next digit is $\lfloor 2f \rfloor$, where $\lfloor \cdot \rfloor$ denotes taking the integer part.
  3. Let $f' = 2f - \lfloor 2f \rfloor$ be the fractional part of $2f$. If $f'=0$ stop, otherwise continue from 1 with $f = f'$.

For example, consider the number $\frac{5}{8}=0.625_{10}$. Then:

  • $2*\frac{5}{8} = \frac{5}{4} = 1 + \frac{1}{4}$, so the first digit is $1$.
  • $2*\frac{1}{4} = \frac{1}{2}$, so the second digit is $0$.
  • $2*\frac{1}{2} = 1$, so the third and final digit is $1$.

In the end, $0.625_{10} = 0.101_{2}$.

For a number with infinite binary expansion, consider $1/3 = 0.333\dotsc_{10}$. Then:

  • $2*\frac{1}{3} = \frac{2}{3}$, so the first digit is $0$.
  • $2*\frac{2}{3} = \frac{4}{3} = 1 + \frac{1}{3}$, so the next digit is $1$.

Since we are left with $\frac{1}{3}$, which is what we started with, we can conclude that the expansion is periodic, thus $0.333\dotsc_{10} = 0.0101\dotsc_{2}$.

$\endgroup$
  • $\begingroup$ Sorry, I don't seem to understand the complexity of this question $\endgroup$ – direprobs May 2 '15 at 19:08
  • $\begingroup$ What do you mean? Could you be more precise as to what you don't understand? $\endgroup$ – A.P. May 2 '15 at 19:31
  • $\begingroup$ I got the idea of positional notation, but I can't understand how did you come up with: $$ 19_{10} = 1 + 2 \cdot \Big(1 + 2 \cdot \big(0 + 2 \cdot (0 + 2 \cdot 1)\big)\Big) $$ $\endgroup$ – direprobs May 2 '15 at 19:51
  • $\begingroup$ I rearranged the previous formula and highlighted the corresponding digits. All you have to do is repeatedly "collect" the $2$s. $\endgroup$ – A.P. May 2 '15 at 20:00
  • 1
    $\begingroup$ Please let me know if this is still unclear. $\endgroup$ – A.P. May 2 '15 at 20:45
0
$\begingroup$

To convert a decimal number into a binary number, decimal number is repeatedly divided by 2 to count the division steps (k) required to reach terminal stage when further division of previously obtained quotient by 2 is not possible. K parameter defines everything about the conversion. For example, k = the number of binary positions for binary digits (0, 1) to fill up to represent the decimal number in binary form accurately. The k value also defines the power of 2 to be assigned to binary digit as per its position value in the stretch of binary digits such that ith binary digit (range of i = 1 to k) is given by 2^ (k-i). If 6 divisions were required for a particular conversion then k = 6; there will be 6 binary positions. The range of power of 2 will extend from 0 to k-1. Highest power of 2 possible for any integer is defined by 2^(k-1). Starting from highest power (left extreme) to right extreme (unit position), powers of 2 will run as 2^(k-1), 2^(k-2),…,2^1,2^0. To fill 6 binary digit positions, powers of 2 to be added run from 2^5 to 2^0 (k= 6). For instance, converting decimal 35 to binary form, we need 6 repeated divisions of 35 by 2 to reach to stage when quotient obtained resists any further division by 2:

Step1 {35: quotient = 35//2 =17, residue =35 % 2 =1} Step2 {17: quotient = 17//2 = 8, residue = 17 % 2 =1} Step3 {8: quotient = 8//2 = 4, residue = 8% 2 =0} Step4 {4: quotient = 4//2 =2, residue = 4 % 2 =0} Step5 {2: quotient = 2//2 = 1, residue = 2 % 2 =0} Ste6 {1: quotient = 1//2 = > 0, residue = 1%2 =1} K= 6. There are 6 binary digits for decimal number 35. Therefore, maximum power of 2 in 35 is 2^(k-1) = 2^5 = 32 The six binary positions represented by string of residues from bottom to top are 100011. There are only 3 positions representing power of 2. These are defined by k values: k=6, k=2, k=1 (from left) representing sum of 2^ (6-1) +2^ (2-1) +2^ (1-1) =32+2+1 =35. To convert any binary number to a decimal number, write down the k values of unity positions in binary digits (counting 1 from right extreme to left), for each position take multiples of 2 for (k-1) times. Applying the rule to cited example: 100011. K=6, 2, 1. It represents sum of: 2^5 + 2^1 + 2^0 =35. The rule extends to any number base system where residues with be in range 0 through (b-1) where b is number base under consideration (3,4,5,6,8,12,16,30,60,...). There too 0 positions are ignored and positions showing residue other than 0 is considered for multiplication by b^(k-1). This is generalized form of representation in terms of repeated divisions or multiplications employing powers of base, and making multiplications or divisions by b. In present case b=2, and the residue to be considered for multiplication is 1.

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