Why Eight Bits Hold 256 Values and Minus 128 Has No Positive Twin

Eight bits are 256 patterns, and a rule decides what they mean. Here are the two rules for whole numbers, the ranges they give, and why one value cannot be negated.

Eight switches, 256 patterns, and no number yet

A byte is eight switches, each independently on or off. Count the patterns by

counting the choices: 2 for the first switch, times 2 for the second, and so on

eight times over, which is $2^8 = 256$ . There are 256 patterns in a byte and

there will never be a 257th.

That count is the whole of what the hardware provides. It does not provide

numbers. A pattern such as 11111111 is eight facts about eight switches, and

nothing in it says whether it is a count, a negative quantity, a letter, or a

colour. A number appears only when a rule is applied, and the rule is a

decision taken elsewhere, in the type of the variable, in the instruction

chosen, or in your own head.

There are two rules for whole numbers in wide use and they disagree about the

same byte. Under the first, 11111111 is 255. Under the second, it is minus 1.

Neither is a mistake and neither is a conversion of the other. They are two

ways of adding up the same bits.

Reading a pattern as a count

The first rule is the one that needs no argument. Each position carries a

weight, the weights are the powers of two, and the value is the sum of the

weights whose bit is set.

FIG 1The place values under each rule

	bit 7	bit 6	bit 5	bit 4	bit 3	bit 2	bit 1	bit 0
weight under the unsigned rule	128	64	32	16	8	4	2	1
weight under the two's complement rule	-128	64	32	16	8	4	2	1

One cell differs between the two rules and it is the ringed one. Under both rules a pattern is read by adding the weights of the bits that are set, with no test of a sign anywhere: 11111111 adds to 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = 255 along the top row, and to -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1 = -128 + 127 = -1 along the bottom. Every surprise later in this course comes from that one sign change.

The largest unsigned value is the pattern with every bit set, so it is the sum

of all eight weights. That sum is worth deriving rather than reading off,

because the same argument gives the answer for any width. Write

$S = 1 + 2 + 4 + \dots + 128$ . Double it, which shifts every term up one place,

giving $2S = 2 + 4 + 8 + \dots + 256$ . Subtract the first from the second and

every term cancels except the two ends, leaving $S = 256 - 1 = 255$ . So the sum

of the weights is always one less than the next power of two, and the largest

unsigned value in $w$ bits is $2^w - 1$ .

Two different facts have now been established and the difference between them

matters. The count of representable values is $2^w$ . The largest representable

value is $2^w - 1$ . They differ by one because zero is one of the values and it

is not at the top.

FIG 2

width in bits	patterns it holds	largest unsigned value
8	256	255
16	65,536	65,535
32	4,294,967,296	4,294,967,295
64	18,446,744,073,709,551,616	18,446,744,073,709,551,615

Each row is the one above it squared, because $2^{16} = (2^8)^2$ and

$65{,}536^2 = 4{,}294{,}967{,}296$ . The third row is the one worth holding on

to. A 32 bit unsigned counter can take 4,294,967,296 distinct values, and the

human population is about 8,000,000,000, so such a counter cannot count people:

$8{,}000{,}000{,}000 / 4{,}294{,}967{,}296 = 1.86$ , which is to say the

population is nearly twice everything the counter can express. Finiteness is

not a vague warning. It is a number, and it is often smaller than the thing

being counted.

Where the negative numbers come from

The obvious way to add negative numbers is to give one bit over to a sign and

read the other seven as a magnitude. That rule exists, it is called sign and

magnitude, and the C standard still names it as one of three permitted

representations. It has two costs that two's complement does not. The pattern

10000000 reads as minus zero, so of the 256 patterns only 255 are distinct

values, and the usable range shrinks to minus 127 through 127. Worse, addition

has to test both signs and decide between adding and subtracting, which is

hardware that does nothing useful.

The rule in use instead changes a single weight. Leave all seven low weights

alone and make the top weight negative.

FIG 3The two's complement reading rule

: the top bit, carrying a weight of minus 128, which is the entire difference from the unsigned rule
: the other seven bits, read exactly as they are read unsigned, contributing somewhere between 0 and 127

Read this as one sum and not as a sign followed by a magnitude. The largest value it can reach has the top bit clear and the rest set, 0 + 127 = 127. The smallest has the top bit set and the rest clear, -128 + 0 = -128. The range minus 128 to 127 is not a convention anyone chose; it is what this sum can produce.

Here $b_i$ is the bit in position $i$ , which is 0 or 1, and $w$ is the width in

bits, which is 8 throughout this section. In general the top weight is

$-2^{w-1}$ , the low bits contribute from 0 up to $2^{w-1} - 1$ , and so the

range runs from $-2^{w-1}$ to $2^{w-1} - 1$ .

At 32 bits that gives the two numbers worth memorising, and both can be checked

by hand from the table above. The 32 bit count of patterns is 4,294,967,296,

half of that is $2^{31} = 2{,}147{,}483{,}648$ , so the top of the signed range

is $2^{31} - 1 = 2{,}147{,}483{,}647$ and the bottom is minus 2,147,483,648.

Why the negative side is one value longer

This is where the counting argument earns its place, because the asymmetry

looks arbitrary and is not. There are 256 patterns. One of them has to be zero,

since arithmetic without zero is not arithmetic. That leaves 255 patterns for

the non-zero values, and 255 is odd, so no rule whatsoever can hand out an

equal number of positives and negatives. The split has to be lopsided by one,

and two's complement puts the extra value on the negative side.

FIG 4Where the 256 patterns land

Count the two shaded stretches. From -128 to -1 inclusive is 128 values, from 0 to 127 inclusive is another 128, and 128 + 128 = 256, which is everything a byte holds. Zero occupies one slot on the right, so only 127 are left for the positive numbers while all 128 on the left are useful. The missing value is positive 128, and that single absence is the whole of the asymmetry.

Notice which side the gap is on. There is a pattern reading minus 128 and no

pattern reading 128. That is backwards from the intuition most people carry,

which is that the negative numbers must be the ones in short supply because the

sign has to be stored somewhere.

Negation is invert and add one, and here is why

The recipe is known by almost everybody who has read about this and the reason

behind it is skipped almost every time. It is three lines of arithmetic.

Take any pattern and call its value $v$ , and write $\lnot v$ for the pattern

with every bit flipped. In each of the eight positions, exactly one of the two

patterns has its bit set, so adding them sets every position once and the result

is 11111111 with no carrying anywhere. Under the signed rule that pattern reads

as minus 1. So

$ $v + \lnot v = -1, \quad \text{hence} \quad \lnot v = -1 - v, \quad \text{hence} \quad \lnot v + 1 = -v.$ $

Inverting overshoots by exactly one, every time, for every value. The add one

is not a convention and not a correction factor fitted to make the examples

work. It is the repair of that offset.

FIG 5Negating 5 in eight bits

step	bit pattern	read as unsigned	read as two's complement	what happened
1	00000101	5	5	The starting value, 4 + 1 = 5. The top bit is clear, so the two rules agree about it.
2	11111010	250	-6	Every bit inverted. As an unsigned count that is 255 - 5 = 250, and as a signed value 250 - 256 = -6, which is one place too far down, exactly as the algebra predicted.
3	11111011	251	-5	Add one. 250 + 1 = 251 unsigned, and 251 - 256 = -5 signed. The answer, reached without anything ever testing a sign.

3 steps

The middle row is the one to look at. Inverting a value does not negate it, it lands one below the negation, because a pattern and its inverse sum to 11111111 and that pattern reads as minus 1. Run the recipe again on 11111011 to check it reverses: inverting gives 00000100, which is 4, and 4 + 1 = 5.

The step from 250 to minus 6 is worth spelling out once, since it recurs

throughout this course. Any pattern's signed reading is its unsigned reading

with 256 subtracted when the top bit is set, because the top bit changes from a

weight of plus 128 to minus 128 and the distance between those is

$128 + 128 = 256$ .

FIG 6Both rules, as two functions

python

def unsigned(bits):
    return sum(int(b) << (len(bits) - 1 - i) for i, b in enumerate(bits))

def twos_complement(bits):
    top = int(bits[0]) << (len(bits) - 1)
    return unsigned(bits) - 2 * top

for pattern in ("11111111", "10000000", "01111111"):
    print(pattern, unsigned(pattern), twos_complement(pattern))

Run this and the three lines printed are 11111111 255 -1, then 10000000 128 -128, then 01111111 127 127. The signed function is the unsigned one with twice the top weight taken off, which is the 256 from the paragraph above written as code. Nowhere does either function examine a sign and branch on it.

The one value that comes back unchanged

Apply the recipe to minus 128, whose pattern is 10000000. Inverting gives

01111111, which is 127. Adding 1 to 127 gives 128, and 128 is not in the signed

range, so what the eight bits actually hold after the increment is 10000000

again. The negation of minus 128 is minus 128.

This is not a flaw in the recipe. No recipe could do better, because by the

counting argument there is no pattern that means positive 128 for it to produce.

The same holds at every width: in 32 bits the negation of minus 2,147,483,648 is

minus 2,147,483,648, and the absolute value of that number is itself. The C

standard records the consequence in a footnote to its own absolute value

function, which says that the absolute value of the most negative number cannot

be represented in two's complement.

There are exactly two values that negation leaves alone. One is zero, which is

no surprise: inverting 00000000 gives 11111111, which is minus 1, and adding 1

returns to 00000000. The other is the most negative value, which is a surprise

every time it is met in a running program, usually in the form of a magnitude

that refuses to become positive.

So a whole number in a machine is three things together: a width, a pattern, and

a rule. The width fixes how many values exist, the rule fixes which values those

are, and the pattern picks one of them. Nothing in that arrangement leaves room

for a 257th value in a byte, which means that any arithmetic whose true answer

is outside the range has to produce something else instead, and what it produces

is entirely predictable. That is where this course goes next.

Recap

A pattern of w bits has exactly 2 to the power w possible values, so eight bits hold 256 of them and 32 bits hold 4,294,967,296, whichever rule is used to read them.
Two's complement gives the top bit the place value minus 2 to the power w minus 1, which is why eight bits run from minus 128 to 127 and the negative side is one value longer than the positive side.
Negating a two's complement value means inverting every bit and adding one, and it returns the wrong answer for exactly one input, the most negative value, which comes back unchanged.

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

NextWhat Happens at the Edge →