Unsigned Integers

AKA Natural Numbers: 0, 1, 2, 3, ..., 2ᴺ-1

This is the same as in your IGCSE studies (but this time with arithmetic) and is required for understanding signed integers, ASCII/Unicode, logic gates, and data streams.

Methods - A quick summary

• Binary to Denary: just add up the powers of 2.
• Denary to Binary: Repeated subtraction of highest power of 2 OR repeated division by 2 to get remainders
• Binary to Hexadecimal and vice versa
  • 1 Nibble = 4 Bits = 1 Hex Digit
• Hexadecimal to Denary: Add up the multiples of powers of 16 OR go via binary.
• Denary to Hexadecimal: Unless it is close to an obvious multiple of 16, go via binary.
• Optional: Binary to and from Octal:
  • 3 Bits = 1 Octal Digit (000 to 111 == 0 to 7)
• Optional: Octal to and from Denary: See Hexadecimal
• Optional: Octal to and from Hexadecimal: Go via binary

Resources - Unsigned Integers

• https://ryanstutorials.net/binary-tutorial
• Worksheets handed out in class - TODO ADD LINKS!
• BBC Bitesize: Introduction to Binary
• Odometer Widget (code.org)
• Binary Game (Cisco / code.org)
• Crash Course CS Ep 4 - Representing Numbers and Letters with Binary

Arithmetic

Good tutorial at Ryans Tutorials: Binary arithmetic

Addition

There are only a few basic additions, then you can use the algorithm (including the carries)

0+0 = 0, 1+0 = 1, 0+1 = 1, 1+1 = 10, 1+1+1 = 11 (carry the 1)

Example:

   111 11  (carries) 

     110010        50

 + 01110111     + 119

 = 10101001     = 169

Subtraction

Easiest to perform by adding negative numbers, see below. For simple examples, it's easy enough to do naively using the standard subtraction with borrowing algorithm:

   1011     11  ( note the borrow from the )

 - 0111    - 7  ( 4th bit to the 3rd bit   )

 = 0100    = 4

Multiplication (Shift and add)

   1101     13  

 x 0111    x 7

---------------  

 +  111   + 21 

   0000     70

  11100

 111000

---------------

1011011     91

Division (Shift and subtract)

1011011 ÷ 11 = 91 ÷ 3 = 30r1

   0͟0͟1͟1͟1͟1͟0͟  r1

11|1011011

   -11

   =101'''

    -11

    =100''

     -11

     =011' 

      -11

      =001

Signed Integers

Good tutorial at Ryans Tutorials: Binary negative numbers

Need to know 4 methods of representing (signed) integers:

• Sign-Modulus (sign bit, used in floating point numbers)
• 1's Complement
• 2's Complement
• Bias (used in floating point numbers' exponent)

We'll work with 8 bit examples, but the same ideas work with smaller and larger word sizes.

Sign-Modulus

So, there is no way of writing a - or + in memory, everything has to be written using binary on/offs. The simplest convention is to interpret the left-most bit (or most-significant bit) as the sign: 0 = + and 1 = -.

The first bit is called the sign bit and the rest is the modulus (another word for absolute value).

E.g.,

• 00100100 = +0100100 = +36
• 10100100 = -0100100 = -36

This simple approach is not that useful for integers as it requires lots of specialised circuitry to implement its arithmetic in hardware. However, it is how the sign is represented in floating point numbers (where specialised hardware is already needed to handle their complexity).

Note, this system has two zeros

• +0 = 00000000
• -0 = 10000000

And it ranges

• from 11111111 = -(2⁷-1) = -127
• to 01111111 = +(2⁷-1) = +127
• In general, it has min/max of ±2^N-1-1

1's Complement

In one's complement we represent a negative number by inverting all of the positive number's bits. E.g.,

• +36 = 00100100
• -36 = 11011011
• 36 + -36 = 00100100 + 11011011 = 11111111

Like the sign-modulus, the first bit indicates the sign of a number and the next 7 bits are used to represent its magnitude.

When we add a number to its negative x + (-x) = 0 using 1s complement, we find that again, like sign-modulus, there is a second representation of zero:

• 0 = 36 + (-36) = 00100100 + 11011011 = 11111111

In 1s complement, arithmetic works almost like it does with positive numbers, with only slight modifications needed at the hardware level. This is why it was used in many early computers although 2s complement is now standard.

Examples:

• 4 + -7 = -3

   4        00000100

+ -7      + 11111000

= -3      = 11111100 → -00000011 = -3

• 7 + -4 = 3

   7         00000111

+ -4       + 11111011

=  3      = 100000010 → 00000011 = 3

Where in the last step the overflow is added back into the least-significant bit in a process called an "end around carry".

• 4 * -3 = -12

   4        00000100

+ -3      * 11111100

=-12    = 1111110000 →  11110011 

                     = -00001100 = -12

Again, the overflow bits are end-around carried.

You can perform subtraction of negative numbers using 1s complement, but that requires end-around borrows and is not fun! It is best to turn a subtraction of a negative into an addition of a positive and just use standard binary addition.

Notes: this system has two zeros

• +0 = 00000000
• -0 = 11111111

And it ranges

• from 10000000 = -01111111 = -(2⁷-1) = -127
• to 01111111 = +(2⁷-1) = +127
• In general, it has min/max of ±2^N-1-1

2's Complement

The end-around carries and borrows of 1's complement make things complicated. 2's complement is designed to work so that overflows can (usually) be ignored!

That is x + (-x) = 100000000 = 00000000 (ignoring overflow). This implies that

• -x = 2⁸ - x = (2⁸-1) - x + 1

Comparing to 1's complement, we see that in 2's complement we represent a negative number by inverting all of the positive number's bits and then adding one. E.g.,

• +36 = 00100100
• -36 = 11011100
• 36 + -36 = 00100100 + 11011100 = 100000000

In 2s complement, arithmetic works exactly like it does with positive numbers, only you discard overflows.

Examples:

• 4 + -7 = -3

   4        00000100

+ -7      + 11111001

= -3      = 11111101 → -00000011 = -3

• 7 + -4 = 3

   7         00000111

+ -4       + 11111100

=  3      = 100000011 → 00000011 = 3

Where in the last step the overflow is discarded!

• 4 * -3 = -12

   4        00000100

+ -3      * 11111101

=-12    = 1111110100 →  11110100 

                     = -00001100 = -12

Again, the overflow bits are discarded.

Subtraction works fine, provided you can borrow from overflow bit - represented in bold on the left of the 7.

   7        100000111

- -5       - 11111011

= 12      =  00001100 = 12

Division with 2s complement also works fine - but it's not needed for this course!

Notes: this system has only one zero

• +0 = 00000000

And it ranges

• from 10000000 = -01111111+1 = -2⁷ = -128
• to 01111111 = +(2⁷-1) = +127
• In general, it has min & max of -2^N-1 & +2^N-1-1.

Why 1s complement works

Represent a number A by

• A = ⁷∑_n=0 a_n 2ⁿ where a_n are the bits:
• A = a₇a₆a₅a₄a₃a₂a₁a₀. a₇ = 0 for a positive 1s C number.

Then -A is represented by

• -A = 0 - A = (2⁸-1) - A = ⁷∑_n=0 (1-a_n) 2ⁿ

Which is the same as inverting all of the bits.

Arithmetic: looking at a subtraction problem we have

• X = -A + B = A' + B = (2⁸-1) - A + B.
• If A > B, then this answer is done as
• X = (2⁸-1) - A + B = (2⁸-1) - (A - B) = (A-B)' = -(A-B).
• If A < B then (2⁸-1) - A + B will "overflow" and not fit in 8 bits. However, but subtracting the "zero" or (2⁸-1), we essentially perform an end-around carry and get
• X = - A + B = (B - A)

Essentially, in 1s complement arithmetic we are working modulo 2⁸-1 = 255 AND identifying 2⁸-1=0.

Why 2s complement works

Represent a number A by

• A = ⁷∑_n=0 a_n 2ⁿ where a_n are the bits:
• A = a₇a₆a₅a₄a₃a₂a₁a₀. a₇ = 0 for a positive 2s C number.

Then -A is represented by

• -A = 2⁸ - A = [(2⁸-1) - A] +1= ⁷∑_n=0 (1-a_n) 2ⁿ +1

The basic idea is that it is arithmetic modulo 2⁸, where for numbers less than 2⁷ you do nothing, for numbers greater than 2⁷, you interpret them by subtracting 2⁸ from them (which modulo 2⁸ is the same as doing nothing!).

E.g., (everything is mod 256)

• 102 - 56 = 102 + (256-56) = 102 + 200 = 302 = 46.
• -21 + 58 = (256-21)+58 = 235 + 58 = 293 = -37

TODO

Essentially, in 2s complement arithmetic we are working modulo 2⁸ = 256 AND that's it!