Binary addition, overflow and shifts

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

F8.4Data representationGCSE15 min

Covers OCR J277 1.2.4 Data storage · AQA 8525 3.3.4 Binary arithmetic · Edexcel 1CP2 2.1.4 Binary addition and shifts · Edexcel 1CP2 2.1.5 Overflow

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Two's complement explained

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:

Sum Result Write Carry
0 + 0 0 0 0
0 + 1 1 1 0
1 + 1 2 0 1
1 + 1 + 1 (with a carry) 3 1 1 
  0101 1010     (90)
+ 0011 0111     (55)
-----------
  1001 0001     (145)
01011010 plus 00110111 added column by column from the right, with the carries above: 10010001, 145carries11111101011010+0011011110010001(90)(55)(145)work from the right
Each 1 above a column is a carry from the column on its right, where 1 + 1 made 2 or 1 + 1 + 1 made 3. Writing the carries in is how you show your working.

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.

200 plus 100 in 8 bits: the last column carries a 1 into a ninth bit that is not there, so only 00101100, 44, is keptcarries1111001000+01100100001011001(200)(100)(44)ninth bit: lostthe 8 bits kept44, not 300: that is overflow
The ninth bit would have been worth 256, and 256 + 44 = 300. With only 8 bits it has nowhere to go, so the answer comes out 256 too small.

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.

13 is 00001101. Shifted left one place it is 00011010, 26; shifted right one place it is 00000110, 6shift left 1: times 2130000110126000110100falls offnew 013 × 2 = 26shift right 1: divided by 213000011016000001101falls offnew 013 ÷ 2 = 6.5, but the 1 that fell off was the half, so 6
Every bit moves one place, into a column worth twice as much (left) or half as much (right), and a 0 fills the gap. A bit pushed off the end is gone for good.

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.