Binary Representation of Decimal Fractions

小数的二进制表示 苏剑林 · 2013-02-05 · Mathematics mathematics number theory

Perhaps your middle-school teacher taught you how to convert decimal numbers like 5, 10, 20, etc. into binary, but did any teacher ever show you how to turn the decimal number 0.1 into a binary fraction?

Here's how we convert a decimal integer into binary: following the rules of decimal arithmetic, we divide the decimal number by 2 to get a quotient and a remainder; divide the quotient by 2 again to get a new quotient and remainder; ...and repeat this until the quotient becomes 0. Then we arrange the remainders obtained at each step in reverse order, and that gives us the binary number. For example, take 6:

$$\begin{aligned}6\div 2=3...0 \\ 3\div 2=1...1 \\ 1\div 2=0...1\end{aligned}$$

Reversed, this gives 110. That's 6 in binary. more

Why does this procedure work? To understand this, we need to start from the method for converting binary into decimal. A binary number $abcde$ is converted into a decimal number via $e+2d+2^2 c+2^3 b+2^4 a$, which follows directly from the rules of binary counting: essentially, a, b, c, d, e represent the digits at positions $10^4 , 10^3 , 10^2 ,10,10^0$ respectively, but binary "10" corresponds to decimal 2, which is exactly how we arrive at the formula above. From the binary-to-decimal method, it's not hard to derive the rule for going the other way: by repeatedly dividing by 2 and computing the remainders, we can recover a, b, c, d, e one at a time.

Integers are manageable enough, but what about fractions? Take $0.1=\frac{1}{10}$, for instance, where $(10)_{10}=(1010)_2$, so we have

$$(\frac{1}{10})_{10}=(\frac{1}{1010})_2$$

If you're comfortable with binary arithmetic, you could just carry out the division $\frac{1}{1010}$ directly within the rules of binary computation to get the binary representation of 0.1. But this is a rather cumbersome approach — the main issue being that most of us aren't fluent in binary arithmetic. So what should we do instead? We can take a roundabout approach. Even without knowing the detailed rules of binary computation, we can readily see that dividing by 10 in binary is just as easy as it is in decimal — it's simply a matter of shifting the decimal point to the left. So instead, we can repeatedly multiply the decimal fraction by 2, take the integer part each time to build up a binary integer, and then repeatedly divide by binary "10" (i.e., shift the point).

Take 0.1 as an example:

$$\begin{aligned}0.1 \times 2^9=51.2 \\ (51)_{10}=(110011)_2 \\ 110011 \div 10^9 =0.000110011\end{aligned}$$

In other words, the decimal number 0.1 is represented in binary as approximately 0.000110011. Interestingly, this process never terminates — meaning that the finite decimal fraction 0.1 becomes an infinitely repeating fraction in binary! That's quite a fascinating fact.

The method described above for converting fractions into binary is admittedly a bit computation-heavy. It can be simplified into a much lighter procedure known as the "multiply by 2 and take the integer part" method:

Multiply the decimal fraction by 2; the integer part of the result is the corresponding binary digit, and the fractional part is carried forward. Then multiply this new fractional part by 2 again, obtaining another integer part and fractional part. Repeat this process until the fractional part becomes 0 or the desired precision is reached. The first integer part obtained is the most significant bit, and the last one obtained is the least significant bit.

For example, with 0.1:

$0.1 \times 2=0.2$, integer part 0, fractional part 0.2;

$0.2 \times 2=0.4$, integer part 0, fractional part 0.4;

$0.4 \times 2=0.8$, integer part 0, fractional part 0.8;

$0.8 \times 2=1.6$, integer part 1, fractional part 0.6;

$0.6 \times 2=1.2$, integer part 1, fractional part 0.2;

...

At this point it starts cycling.

We thus find that the binary representation is 0.000110011..., with a repeating block of 0011. In fact, most finite decimal fractions become infinitely repeating when converted to binary, with the exception of fractions of the form $\frac{1}{2^n}$. Of course, no matter how you convert between the two, an irrational number in decimal will never become a rational number in binary, and vice versa.