Transcript Chapter 3 – Digital Logic and Binary Numbers

Chapter 3 – Digital Logic and
Binary Numbers
These are lecture notes to accompany the book
SPARC Architecture, Assembly Language
Programming, and C,
by Richard P. Paul, 2nd edition, 2000.
By Michael Weeks
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Binary
• A computer is a “bistable” device
• A bistable device:
– Easy to design and build
– Has 2 states: 0 and 1
• One Binary digit (bit) represents 2 possible
states (0, 1)
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
• With 2 bits, 4 states are possible (22 = 4)
Bit1 Bit0 State
0
0
1
Bit2 Bit1 Bit0
State
0
0
0
1
0
0
1
2
0
1
0
3
0
1
2
1
0
3
0
1
1
4
1
1
4
1
0
0
5
1
0
1
6
1
1
0
7
1
1
1
8
• With 3 bits, 8 states are possible (23 = 8)
• With n bits, 2n states are possible
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Binary Coded Decimal (BCD)
• Why not use 4 bits to represent decimal?
•
•
•
•
Let 0000 represent 0
Let 0001 represent 1
Let 0010 represent 2
Let 0011 represent 3, etc.
– This is called BCD
– Only uses 10 of the 16 possibilities
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Binary Number System
• From left to right, the position of the digit
indicates its magnitude (in decreasing order)
– E.g. in decimal, 123 is less than 321
– In binary, 011 is less than 100
• A subscript indicates the number’s base
– E.g. is 100 decimal or binary? We don’t know!
– But 1410 = 11102 is clear
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Bytes
• A group of 8 bits is a byte
• A byte can represent 28 = 256 possible
states
• Registers are usually a multiple of bytes
• SPARC registers have 32 bits (4 bytes)
• 232 = 4,294,967,296
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Memory Addresses
• Memory addresses are in binary
– often 32 bits, these days
– if each memory address maps to 1 byte:
• 232 bytes = 4 GB
•
•
•
•
K = kilo = thousand,
but 1KB actually means 1024 bytes
1MB = 1024 x 1024 bytes
1GB = 1024 x 1024 x 1024 bytes
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Octal and Hexadecimal
• It is difficult for a human to work with long
strings of 0’s and 1’s
• Octal and Hexadecimal are ways to group
bits together
• Octal: base 8
• Hexadecimal: base 16
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Hexadecimal
• With 4 bits, there are 16
possibilities
• Use 0, 1, 2, 3, …9 for the
first 10 symbols
• Use a, b, c, d, e, and f for
the last 6
Bit3 Bit2 Bit1 Bit0 Symbol
0
0
0
0
0
0
0
0
1
1
0
0
1
0
2
0
0
1
1
3
0
1
0
0
4
0
1
0
1
5
0
1
1 0
6
0
1
1
1
7
1
0
0
0
8
1
0
0
1
9
1
0
1
0
a
1
0
1
1
b
1
1
0 0
c
1
1
0
1
d
1
1
1
0
e
1
1
1
1
f
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Binary to Hexadecimal
•
•
•
•
01010110101100112 = ? in hex
Group into 4 bits, from the right:
0101, 0110, 1011, 00112
Now translate each (see previous table):
01012 => 5, 01102 => 6, 10112 => b, 00112 => 3
So this is 56b316
• What if there are not enough bits?
– Pad with 0’s on the left
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Hexadecimal to Binary
• f0e516 = ? in binary
• Translate each into a group of 4 bits:
f16 => 11112, 016 => 00002, e16 => 11102, 516 => 01012
So this is 11110000111001012
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Decimal to Any Number Base
• Take the decimal number, and divide by the
new number base
• Keep track of the quotient and remainder
• Repeat until quotient = 0
• Read number from the bottom to the top
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Decimal to Binary
• Binary is base 2
• Example: convert 35 (decimal) to binary
Quotient
35 / 2 = 17
17 / 2 = 8
8/2=4
4/2=2
2/2=1
1/2=0
Remainder
1
1
0
0
0
1
• So 3510 = 1000112
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Any Number Base to Decimal
• From right to left, multiply the digit of the
number-to-convert by its baseposition
• Sum all results
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Binary to Decimal
• Binary is base 2
• Example: convert 10110 (binary) to decimal
101102 = 1x24 + 0x23 + 1x22 + 1x21 + 0x20
= 1x16 + 0x8 + 1x4 + 1x2 + 0x1
= 16 + 0 + 4 + 2 + 0
=
22
• So 101102 = 2210
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Hexadecimal to Decimal
• Hexadecimal is base 16
• Example: convert 16 (hex) to decimal
1616 = 1x161 + 6x160
= 1x16 + 6x1
= 16 + 6
=
22
• So 1616 = 2210
• Not surprising, since 1616 = 0001, 01102
– If one of the hex digits had been > 9, say c, then we would have
used 12 in its place.
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
ASCII
• American Standard Code for Information
Interchange
• Use byte values to represent characters
• The assembler allows double-quotes
mov
0x4d, %r3
! Moves capital M to register 3
mov
“M”, %r3
! This command does the same
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
ASCII chart
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Bitwise Logical Operations
• There are several binary operations:
–
–
–
–
–
–
NOT
AND
OR
XOR
NAND
NOR
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
NOT
• The NOT operation simply complements a
binary value
– not (a)
– a’
a
not(a)
0
1
1
0
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
AND
• The AND operation uses 2 binary values
– a and b
a
b a and b
0
0
0
0
1
0
1 0 0
1
1
1
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
OR
• The OR operation uses 2 binary values
– a or b
a
b a or b
0
0
0
0
1
1
1 0 1
1
1
1
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
XOR
• The XOR (exclusive-or) operation uses 2
binary values
• True when only one input is true.
– a xor b
a
b a xor b
0
0
0
0
1
1
1 0 1
1
1
0
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
NAND
• The NAND (Not-AND) operation uses 2
binary values
• Take the AND function, and complement it.
– a nand b
a
b a nand b
0
0
1
0
1
1
1 0 1
1
1
0
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
NOR
• The NOR (Not-OR) operation uses 2 binary values
• Take the OR function, and complement it.
• NAND and NOR are easy to make on a chip. Why? Take
CSc 4250 and find out!
a
b a nor b
0
0
1
0
1
0
1 0 0
1
1
0
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Possible Logic Functions
• Suppose you have 2 binary digits: a, b
• Imagine that some function operates on them to
create c.
• What could this function be?
– There are only 16 possibilities
– And some of these are not useful!
a
b
some
c
function
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Logic Operations
A
B
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
0011 Logical
0101
0000 false
0001 a and b
0010 a and (not b)
0011 a
0100 b and (not a)
0101 b
0110 a xor b
0111 a or b
1000 a nor b
1001 a xor (not b)
1010 not b
1011 a or (not b)
1100 not a
1101 b or (not a)
1110 a nand b
1111 true
Sparc
and
andn
xor
or
xnor
orn
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Bitwise
• Each of these logic functions is a bitwise
operation, meaning that the result is independent
of the bits to the left or right
e.g.
101
or 0 1 1
111
• compare this with addition
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Logic Instruction Examples
mov 0x21, %l0
and %l0, 0x3c, %l1
mov 0x21, %l0
or %l0, 0x3c, %l1
mov 0x55, %l0
xnor %l0, 0x3c, %l1
mov 0x55, %l0
xor %l0, 0x3c, %l1
20
mov 0x47, %l0
and %l0, 0xca, %l1
mov 0x47, %l0
andn %l0, 0xca, %l1
42
5
3d
mov 0x47, %l0
or %l0, 0xca, %l1
cf
mov 0x47, %l0
orn %l0, 0xca, %l1
ffffff77
mov
not
ffffffaa
ffffff96
69
0x55, %l0
%l0
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
A Few More Logic Examples
In all the examples below, these registers have the
following initial values:
%l0 = 0x12345678
%l1 = 0x9abcdef0
What are the values for %l1 after the instruction?
and
%l0, %l1, %l1
xor
123456780
or
%l0, %l1, %l1
9abcdef8
%l0, %l1, %l1
88888888
not
%l0, %l1
edcba987
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
SPARC Instruction Format
• These commands are in the form:
command source register 1, source register 2, destination register
command source register 1, immediate value, destination register
• command can be any of the following:
and, andn, xor, or, xnor, orn
• andn means a and (not b)
• orn means a or (not b)
andcc, andncc, xorcc, orcc, xnorcc, orncc
• the cc means “set condition codes”
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
SPARC Logical Instruction
Example
cmp %a_r, 0
ble next
nop
add %b_r, 1, %b_r
next:
This is equivalent to:
if (a > 0)
b++;
%a_r and %b_r will be replaced by the actual registers,
such as %r2 and %r3
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Synthetic Instructions
• The cmp command is a synthetic one. It is a macro
that uses %g0. The above cmp command will be
expanded to:
subcc
%a_r, %g0, %g0
• Also, the tst command compares a register to 0:
tst
%a_r
which the assembler turns into:
orcc
%a_r, %g0, %g0
• Since %g0 ignores any updates, only the condition
codes are affected.
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Flags
• Since individual bits are used to represent
boolean flags, a word may contain 32 flags.
• Common flag operations and mnemonics
– set:
bset
– clear: bclr
– toggle: btog
( done with or )
( done with andn )
( done with xor )
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C
Testing Flags
This command will see if one or more flags is set
btst
reg_or_imm, regrs1
it expands to:
andcc
regrs1, reg_or_imm, %g0
(notice how the operands are switched)
example: test if flag 0x02 is set
btst
0x02, %a_r
be
clear
nop
set:
clear:
Richard P. Paul, SPARC Architecture, Assembly Language Programming, and C