CPX5Binary, Two's Complement, Hexadecimal and Shifts

• A bit (binary digit) is 1 or 0, matching the two electrical states inside a computer: on and off.
• Computers represent, process, store and send all data (numbers, text, sounds, images) and program instructions as binary patterns.
• The same pattern can mean different things: its meaning depends on the context (a number, a character, a colour or an instruction).
• n bits give 2ⁿ different states (patterns). 1 bit gives 2, 4 bits give 16, 8 bits give 256.
• The largest unsigned value is one less: 2ⁿ − 1, because one pattern (all 0s) is used for zero. 8 bits: 256 states, largest value 255.
• Number bases: denary is base 10 (10 digits, 0–9), binary is base 2 (2 digits, 0 and 1), hexadecimal is base 16 (16 symbols, 0–9 and A–F).

Bit

A binary digit: 1 or 0.

Number of states

The number of different patterns n bits can make: 2ⁿ.

An unsigned integer can only be zero or positive. With 8 bits it runs from 0 (0000 0000) to 255 (1111 1111).

• Binary to denary: add the place values wherever there is a 1. 1010 0110 = 128 + 32 + 4 + 2 = 166.
• Denary to binary: work from the left. If the place value fits into what is left, write 1 and subtract it; otherwise write 0.
• Always give 8 bits: keep the leading 0s. 25 is 0001 1001, not 11001.
• Writing it as two groups of four (two nibbles) makes it easier to read and check.

Unsigned integer

A whole number that can only be zero or positive. 8 bits: 0 to 255.

Denary

Base 10, the everyday number system.

A signed integer can be positive or negative. Computers store signed integers in two's complement, where the most significant bit (MSB) has a negative place value.

• In 8-bit two's complement the MSB is worth −128. The other bits are worth 64, 32, 16, 8, 4, 2, 1 as usual.
• If the MSB is 1 the number is negative; if it is 0 the number is zero or positive.
• 1110 0101 = −128 + 64 + 32 + 4 + 1 = −27. (As an unsigned number, the same pattern is 229.)
• Range with 8 bits: −128 (1000 0000) to +127 (0111 1111). That is still 256 values.
• Use unsigned when a value can never be negative (a count of people, a page number): you get twice as many positive values. Use signed when it can be (a temperature, a bank balance, a change in height).
• Negating a number changes its sign, not its size: the negation of 27 is −27.

Signed integer

A whole number that can be positive, zero or negative.

Two's complement

A way of storing signed integers in which the most significant bit has a negative place value (−128 in 8 bits).

MSB

Most significant bit: the leftmost bit, with the largest place value.

• Method 1 (flip and add 1): write the positive number in 8 bits, flip every bit (0 ↔ 1), then add 1.
• Method 2 (copy then flip): starting from the right, copy the bits up to and including the first 1; flip every bit after it.
• Method 3 (place values): put a 1 under −128, then add the positive place values you need to reach the number (−37 = −128 + 91 = −128 + 64 + 16 + 8 + 2 + 1).
• Back to denary: add the place values, using −128 for the MSB.

• Work from the right, column by column, carrying into the next column on the left.
• Write the carries small, above or below the next column: examiners like to see them.
• Subtraction is done by adding the two's complement of the second number: x − y = x + (−y).
• When you subtract this way, there is often a carry out of the MSB. Ignore it: the answer is the 8 bits that are left.

Overflow happens when the result of a calculation is too large to fit in the number of bits available to store it.

• Adding two 8-bit unsigned numbers whose total is more than 255 gives a carry out of the MSB (1 + 1 = 0 carry 1) with nowhere to go.
• The 8 bits that are kept give a wrong answer: 180 + 95 is stored as 19.
• Effects on a program: wrong results or outputs, a value that suddenly “wraps round” to a small number, or an error that stops the program. Not every overflow crashes the program.
• Programs avoid it by using more bits for the variable, or by checking that a result is in range before storing it.

180 + 95 needs a 9th bit: the stored answer is wrong

Overflow

When the result of a calculation is too large to fit in the number of bits available to store it.

In a logical shift, every bit moves left or right by a number of places. Bits that move off the end are lost, and the gaps are filled with 0s.

• On an unsigned number, each place left multiplies by 2: 1 place ×2, 2 places ×4, 3 places ×8.
• Each place right divides by 2: 1 place ÷2, 2 places ÷4, 3 places ÷8.
• A right shift can lose precision: any 1s that drop off the right-hand end are lost, so the answer is rounded down. 0010 0101 (37) shifted right 2 gives 0000 1001 (9), not 9.25.
• A left shift can also go wrong: if a 1 drops off the left-hand end, the result is too big for 8 bits.

Logical shift left by 2: 22 becomes 88

Logical shift

Moving every bit left or right; bits that fall off are lost and the gaps are filled with 0s.

An arithmetic shift right is used on two's complement numbers. The gaps on the left are filled with copies of the sign bit (MSB), so the sign is preserved.

• A positive number has MSB 0, so an arithmetic right shift fills with 0s: the same as a logical shift.
• A negative number has MSB 1, so the gaps fill with 1s and it stays negative: 1010 1100 (−84) becomes 1101 0110 (−42).
• So an arithmetic right shift can divide a negative number by a power of 2.
• An arithmetic shift left can't be relied on to multiply a negative number: bits move into the MSB, so the sign bit isn't preserved. −100 (1001 1100) shifted left one place gives 0011 1000, which is +56.

Logical v arithmetic shift right on a negative number

Arithmetic shift right

Moving every bit right and filling the gaps on the left with copies of the sign bit, so the sign is kept.

Hexadecimal (hex) is base 16. It uses the digits 0–9 and the letters A–F (worth 10 to 15). It is a shorthand for binary.

• Each hex digit stands for one nibble (4 bits), so 8 bits are always 2 hex digits.
• Binary to hex: split into nibbles, convert each nibble (8, 4, 2, 1) to one hex digit. 0110 1110 = 6E.
• Hex to binary: write each digit as a 4-bit nibble. A5 = 1010 0101.
• Why people use it: it is much shorter than binary, so it is easier to read, write and remember, and fewer mistakes are made copying it (memory addresses, colour codes, error codes).
• Hex does not save storage: the computer still stores the binary. Hex is for humans.

One hex digit for each nibble

Hexadecimal

A base 16 number system using 0–9 and A–F, used as a shorthand for binary.

Nibble

4 bits: half a byte, and exactly one hex digit.