ACSL

Assembly — purpose

ACSL assembly is a simplified assembly language where each instruction changes memory, the accumulator, or program flow.

Assembly — program flow

A program normally runs top to bottom unless a branch instruction jumps to a label.

Assembly — ACC

ACC means accumulator; it is the main working register and starts at 0.

Assembly — line format

Each program line has the form LABEL OPCODE LOC.

Assembly — label

A label names a line so branch instructions can jump to it; labels are case-sensitive.

Assembly — opcode

The opcode is the instruction name, such as LOAD, ADD, STORE, PRINT, or END.

Assembly — LOC field

The LOC field is the memory location, label, or immediate value used by the opcode.

Assembly — immediate value

An immediate value starts with =, such as LOAD =123, and means use the number itself.

Assembly — memory location

A memory location stores a value that can be loaded, changed, printed, or used in arithmetic.

Assembly — LOAD X

LOAD X puts the value stored at X into ACC.

Assembly — LOAD =N

LOAD =N puts the number N directly into ACC.

Assembly — STORE X

STORE X copies the current ACC value into memory location X.

Assembly — ADD X

ADD X changes ACC to ACC plus the value of X, usually kept modulo 1,000,000.

Assembly — SUB X

SUB X changes ACC to ACC minus the value of X, usually kept modulo 1,000,000.

Assembly — MULT X

MULT X changes ACC to ACC times the value of X, usually kept modulo 1,000,000.

Assembly — DIV X

DIV X changes ACC to the integer part of ACC divided by X.

Assembly — READ X

READ X reads an input value and stores it in memory location X.

Assembly — PRINT X

PRINT X outputs the value stored at X.

Assembly — DC

DC defines a constant or storage location.

Assembly — END

END stops the program.

Assembly — BG L

BG L branches to label L if ACC is greater than 0.

Assembly — BE L

BE L branches to label L if ACC is equal to 0.

Assembly — BL L

BL L branches to label L if ACC is less than 0.

Assembly — BU L

BU L always branches to label L.

Assembly — tracing strategy

Make a table for ACC and every memory location that changes, then update it line by line.

Assembly — loop strategy

For loops, trace each pass until the branch condition fails or the program reaches END.

Bit-String Flicking — bit string

A bit string is a sequence of 0s and 1s that logical operations can change.

Bit-String Flicking — NOT

NOT flips every bit: 0 becomes 1 and 1 becomes 0.

Bit-String Flicking — AND

AND gives 1 only when both corresponding bits are 1.

Bit-String Flicking — OR

OR gives 1 when at least one corresponding bit is 1.

Bit-String Flicking — XOR

XOR gives 1 when corresponding bits are different.

Bit-String Flicking — padding

When strings have different lengths, pad the shorter one with leading zeroes.

Bit-String Flicking — width

Operations keep the bit-string length unless the problem says otherwise.

Bit-String Flicking — LSHIFT-n

LSHIFT-n shifts bits left n places, drops left bits, and fills right side with 0s.

Bit-String Flicking — RSHIFT-n

RSHIFT-n shifts bits right n places, drops right bits, and fills left side with 0s.

Bit-String Flicking — LCIRC-n

LCIRC-n rotates bits left n places; dropped left bits wrap around to the right.

Bit-String Flicking — RCIRC-n

RCIRC-n rotates bits right n places; dropped right bits wrap around to the left.

Bit-String Flicking — large circulates

For a circulate, reduce n modulo the string length before rotating.

Bit-String Flicking — precedence

Do NOT first, then SHIFT/CIRC, then AND, then XOR, then OR.

Bit-String Flicking — equal precedence

Operators with the same precedence are evaluated left to right.

Bit-String Flicking — unary operators

Unary operators such as NOT bind to the expression immediately after them.

Bit-String Flicking — equation strategy

For unknown bits, name them with variables, apply each operation, then match the required result.

Boolean Algebra — purpose

Boolean algebra works with values 1/true and 0/false.

Boolean Algebra — AND

xy or x·y means x AND y; it is true only when both are true.

Boolean Algebra — OR

x + y means x OR y; it is true when at least one input is true.

Boolean Algebra — NOT

¬x or x with an overline means NOT x; it flips the truth value.

Boolean Algebra — XOR

x ⊕ y is true when x and y are different.

Boolean Algebra — XNOR

x ⊙ y is true when x and y are the same.

Boolean Algebra — precedence

Evaluate NOT first, then AND, then XOR/XNOR, then OR.

Boolean Algebra — truth table method

List all 2^n input combinations and evaluate the expression for each row.

Boolean Algebra — commutative law

x + y = y + x and xy = yx.

Boolean Algebra — associative law

(x + y) + z = x + (y + z), and (xy)z = x(yz).

Boolean Algebra — idempotent law

x + x = x and xx = x.

Boolean Algebra — identity law

x + 0 = x and x·1 = x.

Boolean Algebra — annihilator law

x + 1 = 1 and x·0 = 0.

Boolean Algebra — complement law

x + ¬x = 1 and x¬x = 0.

Boolean Algebra — double negation

¬¬x = x.

Boolean Algebra — absorption law 1

x + xy = x.

Boolean Algebra — absorption law 2

x(x + y) = x.

Boolean Algebra — absorption law 3

x + ¬x y = x + y.

Boolean Algebra — distribution 1

x(y + z) = xy + xz.

Boolean Algebra — distribution 2

(x + y)(x + z) = x + yz.

Boolean Algebra — DeMorgan OR

¬(x + y) = ¬x¬y.

Boolean Algebra — DeMorgan AND

¬(xy) = ¬x + ¬y.

Boolean Algebra — XOR as AND/OR/NOT

x ⊕ y = x¬y + ¬xy.

Boolean Algebra — XNOR relation

x ⊙ y = ¬(x ⊕ y).

Boolean Algebra — simplification strategy

Use identities to remove repeated terms, complements, unnecessary factors, and unnecessary parentheses.

Computer Number Systems — base

A base tells how many digit symbols a number system uses.

Computer Number Systems — binary

Binary is base 2 and uses digits 0 and 1.

Computer Number Systems — octal

Octal is base 8 and uses digits 0 through 7.

Computer Number Systems — decimal

Decimal is base 10 and uses digits 0 through 9.

Computer Number Systems — hexadecimal

Hexadecimal is base 16 and uses 0–9 and A–F.

Computer Number Systems — hex digit values

A=10, B=11, C=12, D=13, E=14, and F=15.

Computer Number Systems — place value

A digit’s value equals digit times base raised to the position power.

Computer Number Systems — convert to decimal

Multiply each digit by its base power and add the results.

Computer Number Systems — decimal to base b

Repeatedly divide by b and read the remainders from bottom to top.

Computer Number Systems — binary to octal

Group binary bits in sets of 3 from the right, then convert each group to one octal digit.

Computer Number Systems — octal to binary

Replace each octal digit with its 3-bit binary form.

Computer Number Systems — binary to hex

Group binary bits in sets of 4 from the right, then convert each group to one hex digit.

Computer Number Systems — hex to binary

Replace each hex digit with its 4-bit binary form.

Computer Number Systems — non-decimal conversions

Converting through binary is usually fastest for octal-to-hex or hex-to-octal.

Computer Number Systems — leading zeroes

Leading zeroes may be added to make binary groups of 3 or 4 without changing the value.

Computer Number Systems — binary addition

Add bits with carries: 1+1=10 and 1+1+1=11 in binary.

Computer Number Systems — binary subtraction

Borrowing in binary means borrowing 10₂, which equals decimal 2.

Computer Number Systems — powers of 2

Know powers of 2 up to at least 4096.

Computer Number Systems — powers of 8

Know powers of 8 up to at least 4096.

Computer Number Systems — powers of 16

Know powers of 16 up to at least 65,536.

Computer Number Systems — fractions

Digits after a radix point use negative powers of the base.

Computer Number Systems — RGB hex colors

A color #RRGGBB uses two hex digits each for red, green, and blue.

Data Structures — stack

A stack is LIFO: last in, first out.

Data Structures — PUSH on stack

PUSH adds an item to the top of a stack.

Data Structures — POP on stack

POP removes and returns the top item of a stack.

Data Structures — queue

A queue is FIFO: first in, first out.

Data Structures — enqueue

Enqueue or PUSH adds an item to the back of a queue.

Data Structures — dequeue

Dequeue or POP removes and returns the front item of a queue.

Data Structures — NIL

NIL is returned when a POP tries to remove from an empty structure.

Data Structures — binary tree

A binary tree is a tree where each node has at most two children.

Data Structures — root

The root is the top node of a tree.

Data Structures — parent and child

A parent points to nodes below it; those nodes are its children.

Data Structures — sibling

Siblings are nodes with the same parent.