Binary, Bitwise Operations and Floating Point

Two's complement

Python's integers can be as big as memory allows. A real processor's cannot: it holds an integer in a fixed number of bits, a word. To see what the hardware does you must keep to a fixed width, and in Python the way is to mask, with & 0xFF for 8 bits.

The problem with signs

How do you store -5 in 8 bits? Using the first bit as a sign, with the other seven for the magnitude, wastes a code on a second zero (+0 and -0) and makes arithmetic awkward, because addition has to check the signs. Two's complement removes both problems.

In two's complement the leftmost bit has a negative place value. In 8 bits the columns are -128, 64, 32, 16, 8, 4, 2, 1. That one change is everything: a number is just the sum of the columns that hold a 1.

To negate a number: invert every bit, then add 1.

def to_twos_complement(value, bits):
    return format(value & (2 ** bits - 1), "0" + str(bits) + "b")

def from_twos_complement(pattern):
    number = int(pattern, 2)
    if pattern[0] == "1":
        number = number - 2 ** len(pattern)
    return number

for value in [5, -5, 127, -128, 0, -1]:
    pattern = to_twos_complement(value, 8)
    print(str(value).rjust(4), pattern, from_twos_complement(pattern))

Negating 5 by hand: 5 is 00000101. Invert it: 11111010. Add 1: 11111011, which is -5. The sum of its columns is -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5.

The range is asymmetric: there is one more negative number than positive, because zero uses up one of the positive codes.

Subtraction is addition

A processor needs no subtraction circuit. To work out 7 - 5, it adds 7 and -5, and ignores the carry out of the top bit.

def from_twos_complement(pattern):
    number = int(pattern, 2)
    if pattern[0] == "1":
        number = number - 2 ** len(pattern)
    return number

a = 7
b = -5
total = (a + (b & 0xFF)) & 0xFF         # add the 8 bit patterns, and keep only 8 bits
print(format(a, "08b"), "+", format(b & 0xFF, "08b"), "=", format(total, "08b"))
print("which is", from_twos_complement(format(total, "08b")))

The sum of the two patterns is nine bits long, 1 00000010. The carry out of the top is thrown away, because the register has only eight bits, and what is left, 00000010, is 2.

Overflow

If the true answer does not fit in the number of bits, the pattern wraps round and the sign is wrong. This is overflow.

def from_twos_complement(pattern):
    number = int(pattern, 2)
    if pattern[0] == "1":
        number = number - 2 ** len(pattern)
    return number

total = (100 + 100) & 0xFF
pattern = format(total, "08b")
print(pattern, from_twos_complement(pattern))

100 + 100 is 200, which is above 127, the biggest 8 bit value. Its pattern is 11001000, which has the sign bit set, so it reads as -56. Adding two positive numbers and getting a negative one is the sign of overflow.

Hexadecimal

Four bits make one hexadecimal digit, so hex is a short way to write binary. It is used for memory addresses, colours and machine code because every byte is exactly two hex digits.

print(hex(255), hex(172), format(172, "08b"))
print(int("AC", 16), int("10101100", 2))
print(format(0b10101100, "02X"))

1010 1100 split into two nibbles is A and C, which is AC.

Bitwise operations

A bitwise operation works on each bit position of its operands separately, as a logic gate does.

a = 0b1100
b = 0b1010
print(format(a & b, "04b"), format(a | b, "04b"), format(a ^ b, "04b"))
print(format(~a & 0b1111, "04b"))
print(3 << 2, 12 >> 2)

~a in Python gives a negative number, since Python's integers have no width, so to see an 8 bit or 4 bit NOT you mask it: ~a & 0b1111.

Shifts

A left shift moves every bit one place to the left, filling with 0. That doubles the number, exactly as adding a zero multiplies a denary number by ten. A right shift halves it, dropping the lowest bit.

x = 5
print(x << 1, x << 2, x << 3)           # 10 20 40: times 2, 4, 8
print(100 >> 1, 100 >> 2, 101 >> 1)      # 50 25 50: divide by 2, 4, and drop the remainder
print((200 << 1) & 0xFF)                 # 144: in 8 bits, 400 overflows and wraps

Masks: reading and changing individual bits

A mask is a number with 1s in the positions you care about. The four masks you must know, applied to a byte called flags:

BOLD = 0b0001
ITALIC = 0b0010
UNDERLINE = 0b0100

style = 0
style = style | BOLD                    # set bold
style = style | UNDERLINE               # set underline
print(format(style, "04b"))             # 0101

print(bool(style & ITALIC), bool(style & BOLD))      # False True

style = style & ~BOLD                   # clear bold
style = style ^ ITALIC                  # toggle italic: it was off, so it comes on
print(format(style, "04b"))             # 0110

Eight yes or no settings fit in one byte this way, instead of eight variables. File permissions work like this, and so do the flags register in a processor and the options passed to many programming functions.

Where else it appears

# Is a number odd? Its lowest bit is 1.
print(7 & 1, 8 & 1)

# Is a number a power of two? Exactly one bit is set, so clearing the lowest leaves nothing.
for n in [8, 12, 64]:
    print(n, n & (n - 1) == 0)

# A subnet mask keeps the network part of an IP address.
ip = (192 << 24) | (168 << 16) | (1 << 8) | 77
mask = 0xFFFFFF00
network = ip & mask
print(".".join(str((network >> shift) & 0xFF) for shift in (24, 16, 8, 0)))

# A colour packed into one number: red, green and blue, a byte each.
colour = (255 << 16) | (128 << 8) | 0
print(hex(colour), (colour >> 16) & 0xFF, (colour >> 8) & 0xFF, colour & 0xFF)

# Parity: XOR every bit, to give a bit that makes the count of 1s even.
def parity_bit(byte):
    bit = 0
    while byte:
        bit = bit ^ (byte & 1)
        byte = byte >> 1
    return bit

print(parity_bit(0b1011001), parity_bit(0b1011000))

# Encrypt with XOR, and decrypt with the same key.
secret = [ord(c) ^ 0b0101 for c in "HELLO"]
print("".join(chr(c ^ 0b0101) for c in secret))

XOR is its own inverse: (x ^ key) ^ key is x. That one property is behind parity checks, simple encryption and the one time pad.

Floating point and characters

Why 0.1 is not 0.1

A computer stores a real number as a binary fraction, and some denary fractions cannot be written exactly as one. A third cannot be written exactly in denary, 0.3333 and so on, and in the same way one tenth is a recurring binary fraction, 0.0001100110011 and so on. It is cut off, and the stored value is a very slightly different number.

print(0.1 + 0.2)
print(0.1 + 0.2 == 0.3)
print((0.1).hex())

import math
print(math.isclose(0.1 + 0.2, 0.3))

Never test floating point numbers for equality. Test whether they are close enough.

Mantissa and exponent

Floating point stores a number the way scientific notation does. It splits it into a mantissa, which holds the digits, and an exponent, which says where the point goes:

value = mantissa × 2 to the power of the exponent

The mantissa gives the precision and the exponent gives the range. With a fixed number of bits in total, adding a bit to the mantissa gives more accurate numbers, and adding one to the exponent gives bigger and smaller ones, and one is paid for by the other.

The A Level format is a two's complement mantissa with the binary point after the sign bit, and a two's complement exponent:

def twos(pattern):
    value = int(pattern, 2)
    if pattern[0] == "1":
        value = value - 2 ** len(pattern)
    return value

def decode(mantissa, exponent):
    m = twos(mantissa) / 2 ** (len(mantissa) - 1)
    e = twos(exponent)
    return m * 2 ** e

print(decode("01101000", "0011"))      # 0.1101 is 0.8125, times 2 to the 3
print(decode("10011000", "0010"))      # a negative mantissa

Normalisation

The same number can be written many ways, as 0.5 × 4 and 0.25 × 8 are both 2. To use the bits of the mantissa properly, a floating point number is normalised: shifted so that the mantissa starts 01 if positive, or 10 if negative. The first two bits are different. Each shift left means the exponent drops by one, so the value does not change.

def twos(pattern):
    value = int(pattern, 2)
    if pattern[0] == "1":
        value = value - 2 ** len(pattern)
    return value

def normalise(mantissa, exponent):
    e = twos(exponent)
    while mantissa[0] == mantissa[1] and "1" in mantissa:
        mantissa = mantissa[1:] + "0"
        e = e - 1
    return mantissa, format(e & 0b1111, "04b")

print(normalise("00011010", "0100"))

00011010 with exponent 4 becomes 01101000 with exponent 2, after two shifts. Both mean 3.25. The normalised form uses all of the precision available.

Seeing the real format

Most computers use the IEEE 754 standard. A 32 bit float is 1 sign bit, an 8 bit exponent and a 23 bit mantissa.

import struct

def float_bits(x):
    raw = struct.unpack(">I", struct.pack(">f", x))[0]
    pattern = format(raw, "032b")
    return pattern[0], pattern[1:9], pattern[9:]

sign, exponent, mantissa = float_bits(0.15625)
print(sign, exponent, mantissa)

Characters

A character is stored as a number. ASCII uses 7 bits, 128 codes, which holds English letters, digits and punctuation. Unicode is a table of more than a hundred thousand characters in every writing system, plus emoji, each with a code point. UTF-8 stores a code point in one to four bytes, and its first 128 codes are identical to ASCII, so every ASCII file is already valid UTF-8.

for character in ["A", "é", "€", "😀"]:
    print(character, ord(character), len(character.encode("utf-8")), "bytes")

Key terms you must be able to define

Two's complement

A way of storing signed integers in which the leftmost bit has a negative place value, so negative numbers are found by inverting the bits and adding one.

Overflow

An error that occurs when the result of a calculation is too large to be stored in the number of bits available.

Bitwise operation

An operation that acts on each bit position of its operands independently, such as AND, OR, XOR or NOT.

Mask

A binary pattern used with a bitwise operation to test, set, clear or toggle selected bits.

Logical shift

Moving every bit of a binary number a number of places left or right, filling the gap with zeros.

Mantissa

The part of a floating point number that holds its significant digits, and so determines its precision.

Exponent

The part of a floating point number that gives the power of two it is multiplied by, and so determines its range.

Normalisation

Adjusting a floating point number so that the mantissa starts with 01 or 10, which maximises the precision.

Rounding error

The small difference between a real number and its stored value, because the number of bits is limited.

Unicode

A character set that gives a unique code point to the characters of nearly every writing system.

Flashcards

Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.

Reach the top grade on this topic

Binary questions are marks for method as well as for the answer, so write every step down.

• Show the working for a negative number: write the positive, invert, add one, then state the answer
• For subtraction, say that the second number is converted to two's complement and added, and that the carry is ignored
• Name the mask, and the operator that goes with it: AND to test or clear, OR to set, XOR to toggle
• In floating point, say that the mantissa decides the precision and the exponent the range
• Check a normalised answer starts 01 or 10, and that the exponent was reduced for each shift left

Mistakes that cost marks here