Sign and magnitude

The most significant bit is the sign (1 = negative); the rest is the size. 1000 0101 = −5. Range −127 to +127, with two zeros; arithmetic is awkward.

Two's complement

The most significant bit has a negative place value (−128 in 8 bits). Range −128 to +127, one zero. To negate: flip all the bits and add 1.

Subtraction

A − B is calculated as A + (−B), using the two's complement of B. Any carry out of the most significant bit is discarded.

Overflow

If the true result is outside the representable range, the answer is wrong, e.g. adding two positives gives a negative.

Floating point

value = mantissa × 2^exponent. Both are usually two's complement; the binary point sits after the first bit of the mantissa.

Normalisation

A normalised mantissa starts 01 (positive) or 10 (negative). This gives maximum precision for the number of bits and a unique representation for each number. To normalise, shift the mantissa and adjust the exponent.

Adding floating point numbers

Make the exponents equal (shift the smaller number's mantissa), add the mantissas, then normalise the result.

Masks

AND clears or tests bits; OR sets bits; XOR toggles bits. Logical shifts multiply or divide by 2.

Character sets

ASCII: 7 bits (128 characters), later extended to 8. Unicode: up to 32 bits, representing characters from all languages plus emoji; the first 128 codes match ASCII.

Arrays, records, lists, tuples

Array: fixed size, one data type, indexed (1D, 2D or 3D). Record: named fields of different types. List: dynamic, can hold mixed types. Tuple: ordered and immutable (can't be changed once created).

Static vs dynamic

A static structure has a fixed size set in advance. A dynamic structure can grow and shrink at run time, using memory from the heap.

Stack

LIFO. Operations: push, pop, peek, isEmpty, isFull. A top pointer tracks the last item. Used for undo, call stacks, backtracking.

Queue

FIFO. Operations: enqueue, dequeue, isEmpty, isFull. Front and rear pointers. A circular queue reuses space: rear = (rear + 1) MOD size.

Linked list

Each node holds data and a pointer to the next node. A start pointer marks the first node, and a free list tracks spare nodes. Items can be inserted and deleted by changing pointers, without moving data.

Trees

A connected graph with no cycles, with a root and nodes connected by branches. In a binary search tree each node has up to two children; left subtree values are smaller, right are larger.

Traversals

Pre-order: node, left, right. In-order: left, node, right (gives sorted order). Post-order: left, right, node.

Graphs

Nodes (vertices) joined by edges (arcs), which may be directed and/or weighted. Stored as an adjacency matrix (fast to check an edge; wastes space if sparse) or an adjacency list (space-efficient for sparse graphs).

Hash tables

A hash function turns a key into an index, so items can be found in (ideally) one step. Collisions (two keys, same index) are handled by, e.g., linear probing or chaining.

De Morgan's laws

¬(A ∧ B) ≡ ¬A ∨ ¬B
¬(A ∨ B) ≡ ¬A ∧ ¬B

"Break the bar, change the sign."

Rules

Distribution: A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
Association: (A ∨ B) ∨ C ≡ A ∨ (B ∨ C)
Commutation: A ∧ B ≡ B ∧ A
Double negation: ¬¬A ≡ A
Absorption: A ∨ (A ∧ B) ≡ A

Karnaugh maps

Cells arranged in Gray code order, so neighbours differ by one variable. Group 1s in rectangles of 1, 2, 4 or 8 (can wrap around edges). Each group gives one simplified term.

Adders and flip-flops

Half adder: S = A ⊕ B, C = A ∧ B. Full adder adds a carry in; full adders chained together add binary numbers. A D-type flip-flop stores one bit, updating only on the rising edge of the clock.