Binary Numbers

"There are 10 kinds of people in the world - those who understand binary and those who don't."

Positional Notation

• Decimal

 Position 7 6 5 4 3 2 1 0 Value 107 106 105 104 103 102 101 100 ... ... ... 10,000 1,000 100 10 1

• Binary

 Position 7 6 5 4 3 2 1 0 Value 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1

 Position 7 6 5 4 3 2 1 0 Value 167 166 165 164 163 162 161 160 ... ... ... 65536 4096 256 16 1

How many digits?

 Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Binary 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F

• Decimal (base 10) requires 10 distinct digits

• Binary (base 2) requires 2 distinct digits

• Hexadecimal (base 16) requires 16 distinct digits - 6 "extra"

Hexadecimal is a convenient shorthand for Binary

• 16 = 24

• Hence one hexadecimal digit represents four binary digits (bits)

• N.B. the value is the same, only how it is represented is different

• Example: What is 15910 in hexadecimal?

15910 = 1001 11112 = 9F16

• Example: What is BA16 in Decimal?

BA16 = 1011 10102 = 18610

• Generally:

 1 byte = 8 binary digits = 2 hexadecimal digits 1 word = 2 bytes = 16 binary digits = 4 hexadecimal digits 1 long word = 4 bytes = 32 binary digits = 8 hexadecimal digits

Representing Data

• Data Types of interest
• Integers (Unsigned/Signed)
• Reals (Floating Point)
• Text

Restricted by a finite number of bits - byte, word, long word

Unsigned and Signed Integers

If only interested in natural numbers, can represent natural numbers by their binary value within the computer. Most computer provide some support for representing and manipulating unsigned integers.

Representation of signed integers is more important.

Several possibilities:

• Sign & Magnitude
• One's Complement
• Two's Complement
• Excess-n (Bias-n)
• Binary-Coded Decimal (BCD)

In any representation, desirable properties are

• Only one bitpattern per value
• Equal number of positive and negative values
• Maximum range of values
• No gaps in the range
• Fast, economic hardware implementation of integer arithmetic

Sign & Magnitude

 Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sign & Magnitude +0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7

• Leftmost ("most significant") bit represents the sign of the integer
• Remaining bits to represent its magnitude
• For n-bits, −(2n−1−1) ≤ S & M ≤ +(2n−1−1)
• Simplest for humans to understand
• Two representations for zero
• Costly to implement

One's Complement

 Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sign & Magnitude +0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7 One's Complement +0 +1 +2 +3 +4 +5 +6 +7 −7 −6 −5 −4 −3 −2 −1 −0

• Negative numbers are the complement of the positive numbers
• −(2n−1−1) ≤ One's Complement ≤ +(2n−1−1) - same as S & M
• Less intuitive (for humans) than Sign & Magnitude
• Less costly to implement
• Bit fiddly

Two's Complement

 Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sign & Magnitude +0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7 One's Complement +0 +1 +2 +3 +4 +5 +6 +7 −7 −6 −5 −4 −3 −2 −1 −0 Two's Complement +0 +1 +2 +3 +4 +5 +6 +7 −8 −7 −6 −5 −4 −3 −2 −1

• Only one bit pattern for zero (ta-da!)
• Hence, asymmetric - one extra negative value
• −2n−1 ≤ Two's complement ≤ 2n−1−1
• Most useful property: X − Y = X + (−Y)
• Hence, no need for a separate subtractor (S & M) or carry-out adjustments (One's Complement)
• Converting from Two's Complement to Decimal, two techniques:

2. Example: 1011 to decimal = −[0100 + 1] = −0101 = −5

3. For n bits, treat leftmost bit as representing a negative number and combine with the positive (unsigned) number represented by the remaining n−1 bits

Example: 1011 = −1000 + 0011 = −23 + 21 + 20 = −8 + 3 = −5

• Converting from Decimal to Two's Complement, corresponding techniques:

1. "subtract one and negate"

Example: −3 = −[0011] => 0010 => 1101

2. For n bits, treat leftmost bit as representing a negative number and combine with the positive (unsigned) number represented by the remaining n−1 bits

Example: −3 = −8 + 5 => 1000 + 101 => 1101

Excess-n (Bias-n)

 Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sign & Magnitude +0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7 One's Complement +0 +1 +2 +3 +4 +5 +6 +7 −7 −6 −5 −4 −3 −2 −1 −0 Two's Complement +0 +1 +2 +3 +4 +5 +6 +7 −8 −7 −6 −5 −4 −3 −2 −1 Excess-8 −8 −7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 7

• Integer N represented by N + n
• For m bits, normally use n = 2m-1
• Like Two's complement, asymmetric
• Used when important to compare and sort numbers easily

Binary-Coded Decimal (BCD)

 Bit Pattern 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 Unsigned 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Sign & Magnitude +0 +1 +2 +3 +4 +5 +6 +7 −0 −1 −2 −3 −4 −5 −6 −7 One's Complement +0 +1 +2 +3 +4 +5 +6 +7 −7 −6 −5 −4 −3 −2 −1 −0 Two's Complement +0 +1 +2 +3 +4 +5 +6 +7 −8 −7 −6 −5 −4 −3 −2 −1 Excess-8 −8 −7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6 7 BCD 0 1 2 3 4 5 6 7 8 9 - - - - - -

• Easy for humans to understand
• Wastes some bit patterns (can use one of them for sign)

[ Index ]

last updated: 19-Oct-06 Ian Harries <ih@doc.ic.ac.uk>