Fixed point and floating point

Binary fractions, mantissa and exponent, normalisation, and adding floating point numbers.

A7.3Data representationA level35 min

Integers are not enough for a robot. Distances, voltages and headings have parts after the point. At GCSE every binary number was a whole number; this lesson stores fractions, first with a fixed binary point and then with a point that "floats", which is how a float in Python is stored.

Binary fractions

Place values carry on halving past the point, exactly as denary places carry on dividing by ten:

That is 4 + 2 + 0.5 + 0.125 = 6.625.

Fixed point

In fixed point the position of the binary point is agreed in advance and never changes. The bits do not store it: the program just knows that, say, the last 4 bits of a byte are the fraction. 01101010 read that way is 0110.1010 = 6.625.

To store a denary value, convert the whole part and the fraction part separately. 3.75 is 3 + 0.5 + 0.25, which is 0011.1100. A quick way to do it in code: multiply by 2 to the power of the number of fraction bits, and store the integer.

def fixed_value(bits, fraction_bits):
    """An unsigned fixed point bit string -> its value."""
    return int(bits, 2) / 2 ** fraction_bits

def to_fixed(value, total_bits, fraction_bits):
    return format(round(value * 2 ** fraction_bits), "0" + str(total_bits) + "b")

print(fixed_value("01101010", 4))    # 0110.1010
print(to_fixed(3.75, 8, 4))           # 0011.1100
print(to_fixed(0.1, 8, 4), fixed_value(to_fixed(0.1, 8, 4), 4))   # 0.1 cannot be stored exactly

Run this in the simulator

Fixed point is fast (it is integer arithmetic underneath) and its precision is the same everywhere, which is why small microcontrollers use it for sensor readings. Its weakness is range: 4 whole bits and 4 fraction bits stop at 15.9375.

Floating point: mantissa and exponent

Floating point stores a number the way scientific notation does: 6.75 is 0.84375 × 2³. Two parts are stored:

• the mantissa, a two's complement fixed point number with the binary point just after the sign bit, so its place values are -1, ½, ¼, ⅛ and so on
• the exponent, a two's complement integer that says how many places to move the point: right for a positive exponent, left for a negative one

The exam boards use small sizes so you can work by hand, typically an 8-bit mantissa and a 4-bit exponent:

Decoding: the exponent 0011 is +3, so move the point 3 places right. 0.1011000 becomes 0101.1000, which is 5.5.

A negative mantissa: 10100000 with exponent 0010. The mantissa is -1 + ¼ = -0.75. The exponent is +2, so the value is -0.75 × 4 = -3.

Encoding 6.75: in binary it is 110.11. Move the point left 3 places to get 0.11011, so the exponent is 3 (0011) and the mantissa is 01101100. For -6.75, take the two's complement of the mantissa: 10010100, with the same exponent 0011.

Normalisation

The same value can be stored many ways: 00010110 0100 and 01011000 0010 both mean 2.75. The first wastes two mantissa bits on leading zeros that could have held more precision. A normalised number uses the whole mantissa:

• a positive normalised mantissa starts 01
• a negative normalised mantissa starts 10

In other words, the first two bits are different. Normalisation gives the greatest precision for the bits available, and it gives each value one representation, which makes comparing numbers straightforward.

To normalise, shift the mantissa left until its first two bits differ, and subtract the number of places shifted from the exponent (the point has to move back to compensate).

A negative mantissa is padded with 1s on the left, so the extra leading 1s are the redundant bits to remove.

Adding and subtracting floating point

To add two floating point numbers:

1. Make the exponents the same, by shifting the mantissa of the number with the smaller exponent right and increasing its exponent.
2. Add the mantissas.
3. Normalise the result.

Example: 01000000 0001 (0.5 × 2 = 1) plus 01000000 0000 (0.5). Shift the second mantissa right one place to exponent 0001: 00100000. Add the mantissas: 01000000 + 00100000 = 01100000, exponent 0001. That is 0.75 × 2 = 1.5, already normalised.

To subtract, add the two's complement of the second mantissa. For 1.5 - 1: both have exponent 0001; 01100000 + 11000000 = 1 00100000, drop the carry, giving 00100000 0001 = 0.5. Normalise: shift left 1 to 01000000 with exponent 0000, still 0.5.

The robot's view

The robot's distance sensor gives a float, which Python stores in 64 bits: 1 sign bit, 11 exponent bits and 52 fraction bits (the IEEE 754 standard, which stores the sign separately rather than using a two's complement mantissa). Exam questions use the small two's complement format above; the ideas of mantissa, exponent and normalisation are the same.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
import math

d = distance()
m, e = math.frexp(d)          # d == m * 2 ** e, with 0.5 <= m < 1: a normalised mantissa
print(d, "=", m, "x 2 **", e)

Run this in the simulator

Task: decode a float

Write two functions.

• float_value(mantissa, exponent): mantissa is a string of 8 characters 0 or 1, a two's complement fixed point number with the binary point after the first bit (place values -1, ½, ¼ down to 1/128). exponent is a string of 4 characters 0 or 1, a two's complement integer from -8 to 7. It returns the value, mantissa × 2 to the power of exponent, as a float.
• is_normalised(mantissa): returns True when the first two bits of the mantissa are different, otherwise False.

The loop prints each line as 01101000 0011 = 6.5 normalised or 00011000 0101 = 6.0 not normalised, with the value exactly as Python prints the float.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def float_value(mantissa, exponent):
    return 0.0

def is_normalised(mantissa):
    return False

for mantissa, exponent in [("01101000", "0011"), ("10110000", "0010"), ("00011000", "0101"), ("11100000", "1111")]:
    word = "normalised" if is_normalised(mantissa) else "not normalised"
    print(mantissa, exponent, "=", float_value(mantissa, exponent), word)

Challenges

1. Write normalise(mantissa, exponent) that returns the normalised pair of strings.
2. Store -0.375 in normalised form with an 8-bit mantissa and 4-bit exponent.
3. What is the largest positive value this 12-bit format can hold, and what is the smallest positive normalised value?