Calculation and theory questions

Number representation, floating point, Boolean logic, state machines and complexity answered quickly and checked.

A15.7Exam preparationA level40 min

Some questions have one right answer that you work out: a binary conversion, a floating point value, a Boolean simplification, the output of a state machine, the complexity of an algorithm. They are quick marks if you are fluent and a trap if you rush. This lesson gathers the methods from across the course and, just as important, the checks that catch a slip before the examiner does.

Always show your working

Calculation questions usually give marks for the method as well as the answer. A wrong final answer with correct working can still earn most of the marks; a wrong answer on its own earns none. Write each step on its own line, and label what it is ("mantissa", "exponent", "move the point 3 places right").

Two's complement

In an 8-bit two's complement number the leftmost bit is worth -128, and the rest are worth what they normally are (lesson A7.2).

11101100 is -128 + 64 + 32 + 8 + 4 = -20.

Check: a leading 1 means negative. To confirm, flip the bits and add 1: 00010011 + 1 = 00010100 = 20. So the original was -20.

Floating point

A normalised floating point number has a two's complement mantissa with the binary point just after the sign bit, and a two's complement exponent saying how far to move the point (lesson A7.3).

Mantissa 01101000, exponent 0011:

1. The mantissa is 0.1101000 = 0.5 + 0.25 + 0.0625 = 0.8125.
2. The exponent is 3, so move the point 3 places right: 0110.1000.
3. That is 4 + 2 + 0.5 = 6.5. (Check: 0.8125 × 2³ = 6.5.)

Mantissa 10100000, exponent 1111:

1. The mantissa is 1.0100000 = -1 + 0.25 = -0.75.
2. The exponent is -1, so move the point 1 place left.
3. The value is -0.75 × 2⁻¹ = -0.375.

Check: a normalised mantissa starts 01 if positive and 10 if negative. If yours starts 00 or 11, it is not normalised, and the question may be asking you to normalise it.

Boolean logic

Build truth tables in a fixed order so no row is missed: count up in binary, A B C from 000 to 111. For NOT (A AND B) OR C:

Check: three inputs means 2³ = 8 rows. When simplifying with identities or De Morgan's laws (lessons A8.3 and A8.4), substitute one row into both the original and your answer; if they differ, a step is wrong. Here De Morgan gives NOT A OR NOT B OR C, which is false only when A = 1, B = 1, C = 0, matching the table.

State machines

To find whether a finite state machine accepts a string, follow it one symbol at a time from the start state, writing the state after each symbol (lesson A6.1). The machine below accepts binary strings with an even number of 1s:

For 1101: even, odd, even, even, odd. It ends in odd, so it is rejected. For 1001: even, odd, odd, odd, even: accepted.

Check: count the 1s directly. Three in 1101, two in 1001.

Complexity

To state an algorithm's time complexity, find how the number of steps grows with the size of the input, n:

• a single loop over the input: O(n);
• a loop inside a loop, each over the input: O(n²);
• halving the problem each step: O(log n);
• splitting in half and doing linear work on each level: O(n log n);
• trying every subset: O(2ⁿ), intractable for large n (lesson A6.7).

Check: ignore constants and lower-order terms. 3n² + 5n + 2 is O(n²).

# fluency check: the same answers, calculated
bits = "11101100"
print(bits, "=", int(bits, 2) - (256 if bits[0] == "1" else 0))
print("0x2F =", int("2F", 16), "=", bin(0x2F))
print("NOT (A AND B) OR C is true in", sum(1 for a in (0, 1) for b in (0, 1) for c in (0, 1) if (not (a and b)) or c), "rows")

Run this in the simulator

Task: theory at speed

Write each method as a function, then print the answers.

• twos(bits): bits is a string of 0s and 1s of any length. Return its value as a two's complement integer: the leftmost bit is worth minus its normal place value.
• float_value(mantissa, exponent): both are strings of bits. The mantissa is two's complement with the binary point just after the leftmost bit; the exponent is a two's complement integer. Return the number's value as a float.
• run_fsm(transitions, state, accepting, text): transitions is a dictionary from (state, symbol) tuples to the next state, state is the start state, accepting is a set of accepting states, and text is a string of symbols. Return True if the machine ends in an accepting state.

Then print exactly these six lines, using the functions for the values:

1. 11101100 = <value> using twos;
2. 01101000 x 2^0011 = <value> and 3. 10100000 x 2^1111 = <value> using float_value;
3. 1101: <result> and 5. 1001: <result>, where the result is accepted or rejected, using run_fsm with the even-number-of-1s machine above (states "even" and "odd", start "even", accepting {"even"});
4. true rows: <n>, counting the rows where NOT (A AND B) OR C is true with three nested loops over A, B and C.

The robot stays still.

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

def twos(bits):
    pass

Challenges

1. Normalise the mantissa 00011010 with exponent 0101, keeping the value the same.
2. Add hex_to_denary(text) without using int(text, 16), and test it on 2F and FF.
3. Design a state machine that accepts binary strings ending in 01, and test it with run_fsm.