Binary and hexadecimal

Inside a computer there is only current flowing or not flowing. So there are just two digits available, 0 and 1, and that is binary. Our own counting, with ten digits, is decimal.

Even with different counting, what a place means works the same way. The 305 of decimal is, from the left, the hundreds, the tens and the units. Move one place to the right and the weight is divided by ten.

In binary that is just divided by two. From the right the weights run 1, 2, 4, 8, 16 and so on, doubling. Grasp this weight per place and you can read any base the same way.

There is only one procedure to remember for decimal to binary. Divide by 2 and write the remainder, then divide the quotient by 2 again. Carry on until it reaches 0, then read the remainders from the bottom up.

Try it with 13. 13 / 2 is 6 remainder 1. Then 6 / 2 is 3 remainder 0. 3 / 2 is 1 remainder 1. 1 / 2 is 0 remainder 1. The quotient has reached 0, so stop.

Reading the remainders from the bottom upwards gives 1101. As you checked on the previous slide, 1101 is 8 + 4 + 1 = 13. Reading from the top gives it backwards, so that is the one thing to watch.

Binary is correct but hard to read at length, like 11010110. So ways of writing it more shortly are used, and one of them is octal.

Since 8 is 2 multiplied three times (2 x 2 x 2), three binary digits are exactly one octal digit. So the conversion needs no arithmetic: cut into groups of three bits from the right and read each group as 0 to 7.

For 011010110, cut into 011, 010 and 110, giving 3, 2 and 6. Put them together for 326.

This notation is still in service. Writing Linux file permissions (read, write and execute, three of them) as 755 is exactly this bundling of three bits into one digit.

Hexadecimal is used even more. Since 16 is 2 multiplied four times, four binary digits (four bits) are exactly one hexadecimal digit.

0 to 9 only gives ten symbols, so 10 to 15 are written a, b, c, d, e and f. f is 15, that is four bits all set to 1.

Now back to #ff0000. A colour holds red, green and blue as eight bits each (= two hexadecimal digits). ff is 1111 1111, which is 255, meaning that colour at full. So #ff0000 is red at maximum with green and blue at 0 — pure red.

The correspondence eight bits = two hexadecimal digits is the answer to why a colour is three pairs of two digits.

A place able to hold one 0 or 1 is one bit. With n bits you can express 2 to the power of n possibilities: 2 with one bit, 16 with four, 256 with eight.

Eight bits bundled together is one byte.

The k, M and G attached to large numbers are, in the binary world, usually counted as 1,024 times rather than 1,000 times (2 to the power of 10). 2 to the 20th is about a million, giving 1M, and 2 to the 30th about a billion, giving 1G.

But if the question says "1M byte = 1,000k bytes", follow that instead. The question specifies which counting to use, and the important thing is not to decide for yourself.

Below the point the thinking is no different from whole numbers. Move one place right and the weight halves. The first is 0.5, the second 0.25, the third 0.125 and the fourth 0.0625.

So 0.1101 in binary is 0.5 + 0.25 + 0.0625 = 0.8125.

Look at the other direction too. Turning the decimal 5.625 into binary: the whole part 5 is 4 + 1, so 101. The fractional part 0.625 is 0.5 + 0.125, so after the point it is .101. Together, 101.101.

One important fact here. The only fractions binary can express are those whose denominator is a power of 2. 0.5 and 0.25 come out exactly, but 0.1 does not. Just as 1 / 3 in decimal never ends at 0.333..., 0.1 goes on for ever in binary.

You cannot write a minus sign in a place holding only 0 and 1. So the leading bit is used as the sign (0 for positive, 1 for negative). The question is what to put inside a negative number.

The plain approach is the ones complement: flip every bit. If 5 is 0000 0101, then -5 is 1111 1010. Simple, but with a snag: both 0000 0000 and 1111 1111 end up meaning 0 (a plus zero and a minus zero).

So what is actually used is the twos complement: flip, then add 1. That makes -5 into 1111 1011.

The reason is clear. Subtraction can be done with nothing but the addition circuit. Add 5 and -5 on paper and, throwing away the overflowing place, you properly get 0000 0000. And there is only one zero. That is why machines choose this one.

There are two ways of holding a fraction. The first is fixed point: decide the position of the point in advance. Settle on "of the eight bits, the top four are the whole part and the bottom four the fraction" and all that is left is laying the bits out. Simple and fast, but the range it can express is very narrow.

The second is floating point: carry the position of the point along too. The number is held in the form m x r^e, where m is the mantissa, r the radix and e the exponent. The radix is normally 2, this being the binary world.

Change the exponent and the point moves freely, so very large and very small numbers both fit in a box of the same size. JavaScript numbers are these.

There is a snag: the way of holding it is not unique (0.101 x 2^3 and 0.0101 x 2^4 are the same value). So there is a rule to line the digits up so the mantissa does not begin with 0, and that is called normalisation.

At last, the second piece of homework.

The box of a floating point number is a fixed size. There is a limit to the digits that fit in the mantissa, so a number that goes on for ever has to be cut off somewhere to go in.

As you saw, neither 0.1 nor 0.2 comes out evenly in binary; both go on for ever. So by the time they are inside the machine both are slightly shifted nearby values. Add two shifted numbers and the answer is shifted too. That is what 0.30000000000000004 really is.

This shift, "arising from rounding, rounding up or rounding down the part below what fits, because the number of digits is limited", is called rounding error. It is not a bug: as long as an endless fraction has to go into a finite box, it cannot be avoided.

So do not use floating point directly for money. Holding it as an integer (in yen or cents) is the standard move.

The exam lines up errors that are easy to confuse with rounding error. Tell them apart by what kind of calculation causes them.

• Loss of significance … happens when you subtract numbers of very close value. The upper digits cancel and all that is left is the slight lower digits. The number of significant digits drops at a stroke
• Loss of information … happens when you add or subtract numbers of very different magnitude. Once the places are lined up, the lower digits of the smaller one are pushed out and vanish
• Truncation error … the shift arising because a calculation that would properly go on for ever is cut off partway. Like stopping pi after a few digits

Telling them apart is short. Digits lost in a subtraction is loss of significance; the smaller one vanishing through a difference in magnitude is loss of information; stopping the calculation is truncation error.

Finally, two ways of measuring the error itself.

• Absolute error … the difference between the true value and the approximation. Plain subtraction
• Relative error … the absolute error divided by the true value. How large a proportion of the original the shift is

The two can come out in opposite orders. Approximating a true value of 1.02 by 1 gives a difference of 0.02; approximating 5.05 by 5 gives 0.05. Looking only at the difference, the first is smaller.

But as proportions, 0.02 / 1.02 is about 0.0196 and 0.05 / 5.05 about 0.0099, so the second is far more accurate.

Misquoting something worth 1 as 1.02 and misquoting something worth a million as a million and two are nowhere near equally bad. Looking at it as a proportion is relative error.