Whole Numbers, and Where They Stop

Last timeLetters as Numbers

A whole number stored in a fixed number of bytes covers a fixed range, and what happens at the end of that range is a wrap rather than an error.

The range a width covers

A whole number is stored in a fixed number of bytes, and that width fixes how

many distinct values it can take. One byte is two hundred and fifty six values,

two bytes is sixty five thousand five hundred and thirty six, four bytes is

about four thousand million, eight bytes is a number large enough that it does

not come up.

The second decision is whether negatives are allowed. If they are, the available

values are split, roughly half below zero and half at or above it, so allowing a

sign does not extend the range downwards for free. It halves the top.

FIG 1The largest positive value, when negatives are allowed

: how many distinct values the width holds
: the largest positive value

The relation being rearranged is that the values are the positives up to M, zero, and the negatives down to one more than M below zero, which is N equals twice M plus two. For four bytes, N is four thousand two hundred and ninety four million and change, and M comes out at 2,147,483,647, a number worth recognising on sight because it turns up in error messages and in dumps. The slight asymmetry, one more negative than positive, is a consequence of zero taking a place on the positive side.

FIG 2Four widths and what each covers

	bytes	values	largest positive with a	largest with no sign
one byte	1	256	127	255
two bytes	2	65536	32767	65535
four bytes	4	4294967296	2147483647	4294967295
eight bytes	8	0	0	0

The last row is coded zero because the eight byte values are too large to print usefully in a table of this kind: the count is about eighteen million million million, and the largest signed value is about nine million million million. The practical reading of the table is the third row, since four bytes is the default width in a great deal of software and 2,147,483,647 is the number that a surprising share of real systems eventually walk into.

What happens at the end

The thing that makes overflow dangerous is that it is not an error. Add one to

the largest value and the arithmetic wraps to the most negative one, quietly,

and the program carries on with a wrong number.

This is a deliberate choice in the hardware. Checking every addition would cost

time on every arithmetic operation in every program, so the hardware wraps and

leaves the checking to anybody who wants it. Some languages check and raise an

error, some wrap silently, and a few grow the number to whatever size is needed,

so the behaviour depends on tools rather than on the idea.

FIG 3A counter in two bytes, approaching the end

step	value before	add one	value after	what the program sees
1	32,765	+1	32,766	nothing unusual
2	32,766	+1	32,767	nothing unusual
3	32,767	+1	-32,768	a count that went negative
4	-32,768	+1	-32,767	the count climbing again, from the wrong place

4 steps

There is no error at any point in this sequence and no log line is written. What the rest of the system sees is a count that was growing and is suddenly negative, which then flows into whatever it feeds: a comparison that was true becomes false, a length that was positive becomes negative, a loop that should run a few more times runs four thousand million more. The third row is where the damage occurs and the fourth is where it becomes hard to diagnose, because by then the value looks ordinary.

The well known instance of this is a count of seconds stored in four bytes with

a sign, which passes 2,147,483,647 in January 2038 and wraps to a date in 1901.

It is the sixth lesson's subject arriving early, and it is being fixed widely by

moving to eight bytes, which postpones the problem by longer than the age of the

universe.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Whole Numbers, and Where They Stop

The range a width covers

What happens at the end

3 more paragraphs to go

This is the reading half

Read alongside