Computer Science I · 120 h · Topic 2 of 6

Number systems and binary arithmetic

Inside the machine everything is bits. What changes is how they are read: the same byte can be an unsigned number, a negative one, a character or an instruction.

Binary Hexadecimal Two’s complement Overflow IEEE 754

01A number is not its notation

Thirteen sheep are thirteen sheep, whether written 13, XIII, 1101 or D. The number is the quantity; what changes is the system used to write it down. The systems used in computing are positional: each digit weighs according to the place it occupies, and the weight of each place is a power of the base b.

\[ N = \sum_{i = -m}^{n -1} d_i \cdot b^i \quad 0 \le d_i \lt b \] n integer digits and m fractional digits. With b = 10 it is everyday arithmetic; with b = 2, the machine’s.

For example, 1101.1₂ = 1·2³ + 1·2² + 0·2¹ + 1·2⁰ + 1·2⁻¹ = 8 + 4 + 1 + 0.5 = 13.5.

Why binary

A circuit that only has to tell two states apart, conducting or not conducting, is cheap, fast and highly immune to noise: a voltage of 4.3 V instead of 5 V is still a “1” beyond any doubt. Telling ten levels apart on a single wire would be far more fragile. Base 2 is not a mathematical choice but an electrical one.

Programmers read binary in groups. Hexadecimal (base 16, digits 0–9 and A–F) condenses four bits into one digit and octal (base 8) condenses three. 1001 1100 reads as 9C at a glance; that is why memory dumps and addresses are written in hexadecimal.

02One byte, many readings

The same eight bits mean different things depending on who reads them. Tap the bits: the pattern stays the same, and the interpretations change all at once. The leftmost bit (b7) is the one with the greatest weight.

Lab · the same byte, six meanings

Click each bit to flip it. In two’s complement, bit 7 weighs −128.

The reading is not in the bits: it is in the program. In C it is decided by the variable’s type, and converting from one type to another often does not touch a single bit; it only changes the reading.

03How to convert between bases

From decimal to another base: successive divisions

Divide by the base and keep the remainder; the quotient is divided again, until it reaches zero. The remainders, read from bottom to top, are the digits.

156 to binary

156 ÷ 2 = 78 remainder 0 · 78 ÷ 2 = 39 remainder 0 · 39 ÷ 2 = 19 remainder 1 · 19 ÷ 2 = 9 remainder 1 · 9 ÷ 2 = 4 remainder 1 · 4 ÷ 2 = 2 remainder 0 · 2 ÷ 2 = 1 remainder 0 · 1 ÷ 2 = 0 remainder 1.

From bottom to top: 156 = 1001 1100₂ = 9C₁₆ = 234₈. Check: 128 + 16 + 8 + 4 = 156.

The fractional part: successive multiplications

Multiply by the base; the integer part that appears is the next digit, and you continue with what remains after the radix point.

0.625 and 0.1 to binary

0.625 · 2 = 1.25 → 0.25 · 2 = 0.5 → 0.5 · 2 = 1.0. It terminates: 0.625 = 0.101₂.

0.1 · 2 = 0.2 → 0.4 → 0.8 → 1.6 → 1.2 → 0.4 → … and 0.4 appears again. 0.1 = 0.00011₂, repeating.

0.1 + 0.2 does not equal 0.3

A fraction has a finite expansion in base 2 only if its denominator is a power of 2. Decimal 0.1 is not, so in the machine it is stored rounded. That is why in almost any language 0.1 + 0.2 == 0.3 is false. Real numbers are never compared with ==: you compare the difference against a tolerance.

Between binary, octal and hexadecimal: grouping

Since 16 = 2⁴ and 8 = 2³, there is no need to go through decimal: the bits are grouped in fours or threes starting from the radix point and each group is replaced. 1011 0110 1111 = B6F; 101 101 101 111 = 5557.

04Binary arithmetic

It works just like decimal, with much shorter tables. In addition, 1 + 1 = 10: you write 0 and carry 1. Multiplication reduces to shift and add, because each digit of the multiplier is 0 or 1: either nothing is added or the shifted multiplicand is added.

    1011   (11)           1011
  + 0110   ( 6)         ×  101
  ------                ------
   10001   (17)           1011    ← 1011 · 1
                         0000     ← 1011 · 0, shifted 1
                        1011      ← 1011 · 1, shifted 2
                        ------
                        110111    (55 = 11 · 5)

Shifting a number k places to the left multiplies it by 2^k; to the right it divides it by 2^k, discarding the remainder. Compilers replace x * 8 with x << 3 when it suits them. The adders that do this in hardware are covered in combinational logic.

05Negative numbers: two’s complement

The machine has no place for the minus sign: everything is bits. There were three solutions, and the one that won is the one that lets you use the same adder for signed and unsigned numbers.

Representation	−5 in 8 bits	Range with 8 bits	Problem
Sign and magnitude	`1000 0101`	−127 … +127	Two zeros (+0 and −0) and a different addition circuit for each combination of signs
One’s complement	`1111 1010`	−127 … +127	It also has two zeros; addition needs to add the end-around carry
Two’s complement	`1111 1011`	−128 … +127	None: a single zero and ordinary addition works

In two’s complement the most significant bit has a negative weight. With n bits:

\[ N = -d_{n -1} \cdot 2^{n -1} + \sum_{i = 0}^{n -2} d_i \cdot 2^i \quad -2^{n -1} \le N \le 2^{n -1} -1 \] To change sign: invert all the bits and add 1. −x = ~x + 1.

One way to see it without formulas: 8-bit numbers form a clock with 256 positions. Subtracting 5 is the same as moving forward 251, because 251 + 5 = 256 wraps around and returns to zero. In two’s complement, position 251 (1111 1011) is called −5. That is why the adder does not need to know whether there is a sign: the count on the clock is the same.

Sign extension

When a signed number is widened to more bits, the sign bit is copied to the left: −5 in 16 bits is 1111 1111 1111 1011, not 0000 0000 1111 1011 (which is +251).

06Carry and overflow: the flags

The result of an 8-bit addition always fits in 8 bits plus a carry. What can fail is the interpretation, and the ALU signals it with flags, without knowing which of the two readings the program cares about:

C (carry): the unsigned result did not fit. 200 + 100 = 300 > 255.
V (overflow): the signed result did not fit. It happens only when adding two numbers of the same sign and getting one of the opposite sign: 100 + 100 gives −56.
N (negative) copies bit 7 and Z (zero) indicates whether the result is 0.

Lab · an 8-bit ALU

Enter the operands in decimal (−128 to 255). The ALU stores them as 8 bits and computes the flags.

A = B =

07Real numbers: fixed point and floating point

In fixed point it is decided in advance how many bits go after the radix point. In the Q8.8 format, for example, a 16-bit integer represents the number divided by 256. It is fast, uses only the integer ALU and is the usual choice in microcontrollers without a floating-point unit; in exchange, the range is small.

Floating point does the same as scientific notation: it stores a sign, an exponent and a mantissa. The single-precision IEEE 754 standard uses 32 bits:

\[ x = {\left(-1 \right)}^s \cdot 1.f \cdot 2^{e -127} \] 1 sign bit s · 8 exponent bits e with bias 127 · 23 fraction bits f. The leading “1.” is not stored: it is implicit.

−6.25 in IEEE 754 single precision

6.25 = 110.01₂ = 1.1001₂ · 2². Sign 1; exponent 2 + 127 = 129 = 1000 0001; fraction 1001 0000 ….

1 10000001 10010000000000000000000 = 0xC0C80000.

With a 24-bit mantissa the relative precision is 2⁻²³ ≈ 1.2·10⁻⁷: about seven decimal digits. Adding 1 to 100,000,000 in a float changes nothing, because the 1 falls below the last digit that is stored. For engineering calculations double is used, with 64 bits and about 16 digits.

08Codes: when bits are not quantities

Code	What it represents	Example
BCD	Each decimal digit in 4 bits. Used by clocks, displays and instruments	59 = `0101 1001`
ASCII	Characters in 7 bits: letters, digits, symbols and control codes	'A' = 65 = `0x41`; '0' = 48
UTF-8	All of Unicode in 1 to 4 bytes; the first 128 coincide with ASCII	'ñ' = `0xC3 0xB1`
Gray	Consecutive numbers differ in a single bit. Avoids false readings in encoders	3 = `010`, 4 = `110`

The digit '7' is not the number 7: it is worth 55. To convert a digit character into its value, subtract '0'. The codes used by converters are covered in A/D and D/A converters.

🔢 Interactive digital logic course The first tab is a binary converter with the weight of each bit in view; the following ones take those bits to gates, Karnaugh maps and flip-flops. ›

09In the lab

Exercise 1 · Seeing the bits in C

Write a function void binary(uint8_t x) that prints the 8 bits using (x >> i) & 1. Use it to print 5, −5 stored in an int8_t, and 251. Explain why the last two coincide.

Exercise 2 · Overflow is real

Declare uint8_t a = 200, b = 100; and store a + b in a uint8_t. Predict the result before printing it (44). Repeat with int8_t and 100 + 100.

Exercise 3 · A float has a limited number of digits

Add 0.1f ten times in a float and compare with 1.0f using ==. Print with %.10f. Repeat with double and propose a correct comparison with a tolerance.

10Common mistakes

Reading the remainders from top to bottom in successive divisions: this gives the number mirrored.
Grouping the bits from the left when converting to hexadecimal. Grouping starts from the radix point.
Forgetting the “+1” of two’s complement, which is the one’s complement.
Confusing carry with overflow. One matters for unsigned numbers and the other for signed ones.
Padding with zeros a negative number when widening it, instead of extending the sign.
Comparing real numbers with ==.

11Self-assessment

Convert 45 to binary, octal and hexadecimal.

45 = 10 1101₂ = 55₈ = 2D₁₆.

What is the value of 1110 0110 unsigned and in two’s complement?

Unsigned, 230. In two’s complement, 230 − 256 = −26.

What is the range of a 16-bit integer in two’s complement?

From −32,768 to +32,767.

When adding 0111 0000 + 0101 0000, which flags are set?

112 + 80 = 192 = 1100 0000. C = 0 (unsigned, it fits), V = 1 (two positives gave a negative: −64), N = 1, Z = 0.

Why is 0.5 stored exactly in a float and 0.2 is not?

0.5 = 2⁻¹ has a finite binary expansion. 0.2 = 1/5 has a 5 in the denominator, which is not a power of 2, and its binary expansion is repeating.

What number does 0x41200000 represent in IEEE 754 single precision?

Sign 0; exponent 1000 0010 = 130 → 2³; fraction 0100… = 0.25. x = 1.25 · 8 = 10.

How do you obtain the numeric value of the character '8'?

By subtracting '0': '8' − '0' = 56 − 48 = 8.

12Further reading

Thomas L. Floyd. Digital Fundamentals. 9th ed. (Spanish edition, “Fundamentos de sistemas digitales”), Pearson Prentice Hall, 2006. Chapter 2 covers number systems, two’s complement, BCD and codes with a great many exercises.
M. Morris Mano. Digital Design. 3rd ed. (Spanish edition, “Diseño digital”), Pearson Educación, 2003. More formal: bases, complements and binary codes as the starting point of logic design.
Randal E. Bryant and David R. O'Hallaron. Computer Systems: A Programmer's Perspective. 3rd ed., Pearson, 2016. Chapter 2 is the best explanation of how C represents integers and floats, with their pitfalls.
David Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic. ACM Computing Surveys, 23(1), 1991. The classic paper on why floating point behaves the way it does.

← Previous topic

Structure of a computer system

Next topic →

Problem solving and algorithm representation