Transcript Lecture #2

Lecture 2: Logic
Bryan Burlingame
08 Feb 2017
Ref: xkcd: www.xkcd.com
Announcements
Homework posted
 Homework 1 due next week
 Lab kit required for lab this week
 Lab 1 is due this week in lab

The Plan for Today



Binary mathematics
Discuss Boolean logic
Briefly introduce flowcharts
 For flowcharts, use a proper graphics program.



Visio is the standard, and is in labs
Gliffy is online, free, and good enough (http://www.gliffy.com)
Don’t use Powerpoint or Word. They are time wasters and
SUPER ugly.
Recall
Computers natively work with on/off, 0/1,
binary numbers
 Binary is similar to decimal





Binary: base 2
Decimal: base 10
2,54610 = 2 x 103 + 5 x 102 + 4 x 101 + 6 x 100
10112 = 1 x 23 + 0 x 22 + 1 x 21 + 1 x 20 = 1110
Binary to Hexadecimal

Hexadecimal (base 16) is a convenient
numbering system

0 – 9, A – F (A = 1010, B = 1110, etc
Observe 24 = 16, allows four bits (a nyble)
to be grouped
 11002 = 1210 = 0xC16

Binary to Hexadecimal
Convert Binary to Hex
 1100001110011111b

Binary to Hexadecimal
Convert Binary to Hex
1100 0011 1001 1111 b
12
3
9
15 d
C
3
9
F h

(grouping 4 bits)
C39Fh
 C * 163 + 3 * 162 + 9 * 161 + F * 160 =
50,079
 12 * 163 + 3 * 162 + 9 * 161 + 15 * 160 =
50,079

Representations
Decimal (default)
Binary
Hexadecimal
108
0’01101100
0x6C
108d
0110 1100b
6Ch
10810
0110 11002
6C16
108 dec
0110 1100 bin
6C hex
Group by 3s with a
comma
Group by 4s with a
space or an underbar
Generally don’t group
Spoken short form
Decimal to binary

Many ways, this is how I do it

120





120 < 128, 0 in 7th position
120 > 64, 1 in 6th position
 120 – 64 = 56
56 > 32, 1 in 5th position
 56 – 32 = 24
24 > 16, 1 in 4th position
 24 – 16 = 8
8 = 8, 1 in 3rd position




8–8=0
Binary
Decimal
1
1
10
2
100
4
1000
8
10000
16
100000
32
1000000
64
10000000
128
Once we hit zero, all other values are zero
0111 1000
Why do I do it this way? It is quick when I don’t have a
calculator. Your mileage may vary
Bitshifts (<< Left Shift, >> Right Shift)
A bit shift shifts bits in a direction
 Left shift shifts bits to the left and simulates a
multiply of 2
 Right shift shifts bits to the right and simulates
an integer division of 2
 Bits outside the range are lost
 23 << 3 = 184 (left shift by 3)
0001 0111 shifted = 1011 1000
 23 >> 2 = 5 (right shift by 2)
0000 0101 = 5 (note the last two bits are lost)

Bitwise arithmetic
Mimics digital hardware
 Based on Boolean logic
 Operates on each bit within a number


(i.e. operates bitwise)
Many, many hardware peripherals take
advantage of bitwise operations
 Implemented directly in hardware


Very fast
True and False
Generally, false is zero and true is notzero
 Usually, all comparisons which are true
generate a 1
 (23 > 4) = 1
 This comes up a lot!

Binary (Bitwise) And - &
Y
&
0
1
X 0
1
0
0
0
1
194 & 225 = 227
1100 0010 (194)
&
1110 0001 (225)
-------------------------------1100 0000 (192)
Binary And is commonly
used with “bitmasks”
A binary & used with a
bitmask can ensure that a
given bit is turned “off”
& is shift + 7
Binary (Bitwise) Or - |
Y
|
0
1
X 0
1
0
1
1
1
194 | 225 = 227
1100 0010 (194)
|
1110 0001 (225)
-------------------------------1110 0011 (227)
Binary OR, is, also,
commonly used with
“bitmasks”
A binary | used with a
bitmask can ensure that a
given bit is turned “on”
| is shift + \
Binary (Bitwise) Xor - ⊕
Y
⊕
X 0
1
0
1
0
1
1
0
194 ^ 225 = 35
1100 0010 (194)
⊕
1110 0001 (225)
-------------------------------0010 0011 (35)
Xors are commonly used to
switch the values of selected
bits or to test for
inequivalence
C uses ^ for Xor
^ is shift + 6
Binary (Bitwise) Not (complement) - ~
~
X 0
1
1
0
194 ^ 225 = 35
~
1100 0010 (194)
---------------------------0011 1101 (61)
Complements simply flip the
bits (turn 0’s into 1’s and 1’s
into 0’s)
C uses ~ for complement
~ is shift + ` (next to 1)
Order of operations – C & Matlab
Operators
*/%
Multiplication, division, modulo (integer) division
+-
Addition, subtraction
<<
>>
Left bitshift, right bitshift
&
Bitwise and
^
Bitwise xor
|
Bitwise or
Boolean Logic
And &&
False
True
False
False
False
True
False
True
False
True
False
False
True
True
True
False
False
True
False
False
True
True
True
True
Exclusive Or (Xor) ^^
Or ||
Boolean Logic - Examples
By convention, 0 is false. Nonzero is true.
 ( 6 < 14 ) && ( 9 > 5 )
 5 || (19 > 45) && (57 < 108)
 (My name is Bryan) && (This is ME30)

(name == “Bryan”) && (class == “ME30”)
((16 + 45) == 61) ^^ ((49) == (7 * 7))
 42

Flowcharts - 1

Flowcharts

A graphical tool that diagrammatically depicts
the steps and structure of an algorithm or
program
Symbol
Name/Meaning
Symbol
Meaning
Process – Any type of internal
operation: data transformation,
data movement, logic operation,
etc.
Connector – connects sections
of the flowchart, so that the
diagram can maintain a smooth,
linear flow
Input/Output – input or output
of data
Terminal – indicates start or
end of the program or algorithm
Decision – evaluates a condition
or statement and branches
depending on whether the
evaluation is true or false
Flow lines – arrows that
indicate the direction of the
progression of the program
Flow control

These Boolean operations are used along
with flow control (or branching)
statements to control the flow of a program
True
Decisions
False
References

Nicholas, P. (1994). Digital Design. Minneapolis/St. Paul: West
Publishing Company