Binary addition, overflow and shifts

Adding in binary with carries, overflow, and shifting to multiply and divide.

F8.4Data representationGCSE15 min

A processor does arithmetic in binary. This lesson adds binary numbers the way the processor does, sees what happens when the answer is too big for the bits available, and meets the fastest multiplication there is: shifting.

Adding binary

Binary addition works like column addition in denary, from right to left, carrying when a column is too big. There are only four sums to know:

  0101 1010     (90)
+ 0011 0111     (55)
-----------
  1001 0001     (145)

In Python, the column method is a loop from the right with a carry:

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

def add_binary(a, b):
    """Add two 8-bit strings column by column. Returns (8-bit answer, carry out of the last column)."""
    result = ""
    carry = 0
    for i in range(7, -1, -1):              # the rightmost column first
        total = int(a[i]) + int(b[i]) + carry
        result = str(total % 2) + result    # write the 0 or 1
        carry = total // 2                   # carry the 2s
    return result, carry

answer, carry = add_binary("01011010", "00110111")
print(answer, "=", int(answer, 2), "carry out:", carry)

Run this in the simulator

Overflow

Eight bits hold at most 255. Add 200 and 100 and the true answer, 300, needs nine bits:

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

def add_binary(a, b):
    result, carry = "", 0
    for i in range(7, -1, -1):
        total = int(a[i]) + int(b[i]) + carry
        result = str(total % 2) + result
        carry = total // 2
    return result, carry

answer, carry = add_binary(format(200, "08b"), format(100, "08b"))
print(answer, "=", int(answer, 2))
if carry:
    print("OVERFLOW: the answer needed a ninth bit")

Run this in the simulator

The eight bits that are kept say 44, not 300. When a result is too large for the bits available, the extra bit is lost: that is overflow. A processor sets a flag when it happens, so a program can notice. A robot's odometer that counted in one byte would roll over from 255 to 0 and suddenly think it had gone backwards.

Shifts

Moving every bit one place to the left doubles a number, just as moving denary digits left multiplies by ten. Moving them right halves it:

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

n = 13
print(format(n, "08b"), n)
print(format(n << 1, "08b"), n << 1, "shifted left 1: times 2")
print(format(n << 2, "08b"), n << 2, "shifted left 2: times 4")
print(format(n >> 1, "08b"), n >> 1, "shifted right 1: divided by 2, the remainder lost")

Run this in the simulator

<< shifts left and >> shifts right. Shifting left by n places multiplies by 2 to the power n; shifting right divides, and any bits pushed off the right-hand end are lost, so 13 shifted right once is 6, not 6.5. Shifting is much faster for a processor than multiplying, which is why it matters.

A left shift can overflow too: bits pushed off the left of an 8-bit number are lost.

Task: an 8-bit adder

Write add_binary(a, b) yourself (no int(..., 2) or bin inside it) that adds two 8-bit strings and returns the 8-bit answer and the carry out. Print 01011010 + 00110111 = 10010001 and, on the next line, 11001000 + 01100100 = 00101100 overflow, working both answers out with your function.

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

def add_binary(a, b):
    return "00000000", 0

Challenges

1. Add three 8-bit numbers with your function, and check when overflow happens.
2. Write shift_left(bits) on strings: drop the first character and add a 0 at the end. Check it doubles the number.
3. Why does shifting right lose information? Find a number that shifting right then left does not bring back.