Binary and two’s complement

A computer stores every whole number as a row of bits: digits that are 0 or 1. This lesson shows how a row of bits stands for a number, how negative numbers are stored, and what happens when a number does not fit. The rest of this station builds on it.

Places worth powers of 2

In the numbers we write every day, each place is worth ten times the place on its right: ones, tens, hundreds. In binary, each place is worth two times the place on its right: 1, 2, 4, 8, 16, and so on. Each digit is a bit, 0 or 1.

Number the places from the right, starting at 0. Place k is worth 2ᵏ, which means k twos multiplied together: place 3 is worth 2³ = 8, and place 0 is worth 2⁰ = 1. A number is the sum of the worths of the places that hold a 1. So 101101 is 32 + 8 + 4 + 1 = 45.

To write a number in binary, look at its last bit first. A number is odd exactly when place 0 holds 1, because every other place is worth an even amount. Then halve the number, rounding down: this removes place 0, and every other bit moves one place to the right. Repeat until nothing is left. In this station, bits are always written highest place first, as Python prints them, and the plate over each bit is its place number, so place 0 is at the right.

How many places does a number need? With k places you can write every number from 0 to 2ᵏ − 1, which is 2ᵏ numbers in all. So a number x above 0 needs ⌊log₂ x⌋ + 1 places. Here log₂ x is the power you must raise 2 to in order to get x (how many times you can halve x before you reach 1), and ⌊ ⌋ means “round down”. 45 lies between 2⁵ = 32 and 2⁶ = 64, so it needs 6 places.

Binary in Python

bin(45)              # '0b101101'  (0b means binary)
0b101101             # 45: a binary number in code
int("101101", 2)     # 45: read a string of bits
format(45, "08b")    # '00101101': 8 places, 0s in front
f"{45:08b}"          # the same, in an f-string
(45).bit_length()    # 6: the places 45 needs

Hexadecimal (base 16) writes four bits as one digit, 0 to 9 then a to f: 0xFF is 255, which is eight 1s, and 0x2D is 45. It is a short way to write long rows of bits, so masks are often written in it.

A fixed number of bits

A processor works on rows of a fixed length: 8, 16, 32 or 64 bits. A row of 8 bits is a byte. An 8-bit row holds 0 to 255. Add 1 to 255 (eight 1s) and every place carries; the last carry has no place to go and is dropped, so the result is 0. In other words, fixed-width arithmetic keeps only the remainder after dividing by 2⁸ = 256. Languages such as C, Java and Go, and libraries such as NumPy, work this way.

Python’s own whole numbers are different: they grow to as many bits as they need. 2 ** 100 is exact. To get the fixed-width result in Python, keep the lowest bits yourself with a mask (lesson 3): (255 + 1) & 0xFF is 0.

Negative numbers

A simple idea is to use the top bit for the sign and the rest for the size. It has two problems: there are two zeros (+0 and −0), and adding a negative number needs different rules from adding a positive one. Computers use a better scheme called two’s complement.

Here 2ʷ⁻¹ means 2 to the power w − 1. In 8 bits the top place, place 7, is worth −128. So 11111010 is −128 + 64 + 32 + 16 + 8 + 2 = −6, and 01111111 is 127. The 8-bit numbers run from −128 (10000000) to 127. The top bit still tells you the sign: it is 1 exactly for the negative numbers.

To negate a number, flip every bit and add 1. Why does this work? Flipping every bit of x gives a number ~x (read “not x”) whose bits are 1 exactly where x has 0. So x + ~x has a 1 in every place, and all 1s is −128 + 127 = −1. From x + ~x = −1 we get ~x = −x − 1, so −x = ~x + 1. The second version of the figure steps through −6.

The great advantage is that adding works the same way for every number. The circuit that adds two rows of bits needs no special case for negative numbers: in the figure, 6 + (−6) gives 0 once the carry out of the top place is dropped. Subtraction is adding the negation.

Fixed widths can still overflow. In 8 bits, 127 + 1 is 10000000, which is −128, as the third version of the figure shows. In 32 bits, 2,147,483,647 + 1 becomes −2,147,483,648. Overflow causes real bugs: a 32-bit counter of milliseconds runs out after about 24.8 days, and the middle of a binary search, (lo + hi) / 2, can overflow in C or Java when lo and hi are large (BSRC-6 gives the usual fix, lo + (hi − lo) / 2, for those languages).

Python’s endless bits

Python’s whole numbers have no top place, so how can they be negative? Python’s bit operators act as if every number had endless bits to the left. A number that is 0 or more has endless 0s there. A negative number has endless 1s: −6 is …11111010. This is two’s complement with no width at all, and every rule above still holds. In particular, ~x is always -x - 1.

~6                # -7
-6 & 0xFF         # 250: the lowest 8 bits of -6
bin(-6 & 0xFF)    # '0b11111010'
bin(-6)           # '-0b110': a sign and the size,
                  # not the bit pattern

Note the last line: bin of a negative number prints a minus sign and the bits of its size, not the two’s complement pattern. To see the pattern, mask it to a width first. Masking also works on numbers too big for that width: the mask keeps the lowest bits, exactly as a fixed-width machine does.

Now try BITS-P1, Wrap to w bits: what does a w-bit machine store for any whole number?