Binary arithmetic and signed integers

Unsigned addition and multiplication, sign and magnitude, two's complement, subtraction and overflow.

A7.2Data representationA level30 min

At GCSE you added 8-bit numbers, spotted overflow and met two's complement. A level asks for more: the range of an n-bit number as a formula, binary multiplication, a second way to store negatives (sign and magnitude), subtraction done by adding, and exactly when a signed result has overflowed. The robot's motor commands are signed bytes, so these rules decide whether "reverse at 50" arrives as reverse at 50.

Unsigned binary

Unsigned binary has no sign: every bit has a positive place value. With n bits the smallest value is 0 and the largest is 2ⁿ - 1, so 8 bits hold 0 to 255 and 16 bits hold 0 to 65,535.

Addition works column by column from the right. Each column adds two bits and a carry: the column's answer is the total mod 2 and the carry is the total divided by 2.

  01011011    (91)
+ 00110110    (54)
  111111      carries
----------
  10010001    (145)

If a carry comes out of the leftmost column the answer needs more bits than there are: in unsigned arithmetic that is overflow.

Multiplication is shift and add, the way long multiplication works in denary. For each 1 in the multiplier, write the other number shifted left by that bit's position, then add the rows.

      00001101    (13)
    x 00000110    (6)
    ----------
      00011010    13 shifted left 1 (bit 1 of 6 is set)
    + 00110100    13 shifted left 2 (bit 2 of 6 is set)
    ----------
      01001110    (78)

Sign and magnitude

The simplest way to store a negative: use the leftmost bit as a sign (0 positive, 1 negative) and the other bits as the size, the magnitude.

It is easy for people to read, but it has two problems. There are two zeros, so 8 bits only reach -127 to +127. And ordinary addition gives wrong answers: 00000101 + 10000101 is 10001010, which reads as -10, not 0. A processor would need separate circuits for signs.

Two's complement

In two's complement the leftmost bit has a negative place value. For 8 bits the places are -128, 64, 32, 16, 8, 4, 2, 1, so the range is -128 to 127. For n bits the range is -2ⁿ⁻¹ to 2ⁿ⁻¹ - 1. There is one zero, and the same adder works for positive and negative numbers.

To negate a number: flip every bit and add 1. Or, from the right, copy up to and including the first 1, then flip the rest. Both work in either direction, from positive to negative or back.

Subtraction is adding the negative. To work out 50 - 25:

   25 = 00011001  ->  flip 11100110  ->  add 1  ->  11100111  (-25)

   00110010    (50)
 + 11100111    (-25)
 ----------
 1 00011001    (25, and the carry out of the left is discarded)

def to_twos(n, bits=8):
    """-2**(bits-1) to 2**(bits-1)-1 -> a two's complement string."""
    return format(n & (2 ** bits - 1), "0" + str(bits) + "b")   # masking with 11111111 keeps the low 8 bits

def from_twos(text):
    value = -(2 ** (len(text) - 1)) if text[0] == "1" else 0
    return value + int(text[1:], 2)

for n in [25, -25, 127, -128]:
    print(n, to_twos(n), from_twos(to_twos(n)))
print(from_twos("1111111111111011"))    # 16 bits, still -5

Run this in the simulator

Carry is not overflow

With signed numbers a carry out of the leftmost column is normal and is thrown away, as in 50 - 25 above. Overflow is something else: the true answer is outside -128 to 127, so the sign bit of the result is wrong. It can only happen when both inputs have the same sign and the answer's sign is different.

A processor records both in its status register as separate flags (C for carry, V for overflow), which is how a program can tell them apart.

Here is why that matters on a robot. A controller adds a correction to a signed speed byte: 112 + 48 should be 160, but 160 does not fit in a signed byte, so the motors receive -96 and the robot reverses at full tilt.

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

def wrap8(n):
    """What an 8-bit signed register really holds after n is stored in it."""
    return (n + 128) % 256 - 128

speed = wrap8(112 + 48)
print("stored speed:", speed)
if speed < 0:
    backward(min(-speed, 100), distance=10)

Run this in the simulator

Hexadecimal and signed values

Hex is still a shorthand for the bit pattern, not the value. 9C is 10011100, which is 156 unsigned but -100 in two's complement. When you read a byte in hex you must know whether it is meant to be signed. Convert hex to binary one digit (four bits) at a time, then apply whichever representation the byte uses.

Task: a signed adder

Write add8(a, b). Each parameter is a string of exactly 8 characters, each 0 or 1, holding an 8-bit two's complement number. It returns a tuple (total, carry, overflow):

• total: the 8-character bit string of the sum, with any carry out of the leftmost column dropped
• carry: the carry out of the leftmost column, the integer 0 or 1
• overflow: True when both inputs have the same sign bit and total has the other one, otherwise False

Add column by column from the right; do not convert to denary with int(..., 2), bin or format. The loop prints each line as 01110000 + 00110000 = 10100000 carry 0 overflow True.

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

def add8(a, b):
    total = ""
    carry = 0
    # add the columns from right to left here
    return total, carry, False

tests = [("01110000", "00110000"), ("11111011", "00000101"),
         ("10000000", "11111111"), ("00101101", "11110110")]
for a, b in tests:
    total, carry, overflow = add8(a, b)
    print(a, "+", b, "=", total, "carry", carry, "overflow", overflow)

Challenges

1. Write sub8(a, b) that uses add8 and your own negate function, and test 50 - 25 and -100 - 100.
2. Write mul8(a, b) for unsigned bytes by shift and add. When should it report overflow?
3. Why can a positive number added to a negative number never overflow?