Representation
57656c636f6d6520746f20435335303032210a
Northeastern
Discrete Structures
Copyright By PowCoder代写 加微信 powcoder
everything
is represented with
physically
numbers These – values are
like tiny switches o n off
characters implemented transistors
w h ic h a c t switch
aiierything.
Tru e False +su ou
demagnetized
C irc u it
magnetized
= 0 or digIT ” 1
1 character of text data
1256 possible values )
1000^1{fn 10
2 D-ima.IM,
left shift
8792 = 8 ✗ 10
7×102+9×10 -12×100
1001 / [Base
32 ⇒ 320 (
Places = / OX
8792,0 = 879 • 10 +2
= (87.10-19) . 10 1- 2
((((8.10)-17)- to+9). 10 1-2
=X.X-X…. In
10 . 10.10
xaxb-xa-b.IT
22.23=4 -8=32–27 3–43–64=26 ✓
‘ 1,06 11,000
thousandth 1/8 ( m illi )
2 11,00 hundredth 1/4
100=1 o n e
1 10 tens 2
2 1 0 0 hundreds
thousands 8
1000000 millions 64
109 billions 512
200=104857621 million
40 240 = tera
working the other way ”
8792 as a sequence of
Its value is
8000 1- too 1- 90
= 80-17= 87
870+9–879
879×10+2 = 87901-2 = 8 7 9 2
Powers of Two
Binary⇒ Decimal 24 ‘ ‘ ‘ zzz
I01102= 1 O l l 0
zero one one zero
” 16s 8s 4s 2s
I ✗ 2″ -10×23+1×22 -1 I ✗2′ + 0×20
= 16 + 0 + 4 + 2 1- 0
We can shift an add as we did
now a shift left multiplies by 2 and we add 10-0
10 = 1×21-0 = 2
=5✓ 101I =5×21-1=11
11×2+0–22,0
Decimal → Binary (Two
32 16 8 4 2 1
41,0 = 10.10012
I→2→5→ to→
I – I = 0 (Done)
32 16 8 4 2
27-16=11 I1 011
3-2 = I 27,0= 1 I 0112
32 16 8 4 2 1
Approach : odd : write down 1 , compute/X-D:-c
: write down 0, compute ✗ ÷2 significant
20 O f d’S’t ,oo
significant
1 : add powers of 2 together
I0I1Oz⇒ 2t2 +2
= 16 1- 4 1-
multiplyby2 and add 0 or 1
0 I ✗ 2 1- 0 = 2
LSB 0 11 ✗ 21-0=22
A bigger example :
64 32 16 8 4 2 I
⇒ 64-132-1 8 + I = 105
I 1×2-11=3
Additionandswbtraqtion
122⇒ olI0 = I6
Things every
scientist should know
Counting : 0 0 0 0 0 I 0001
10^-1 5 01 01 ndigits:0to 6 0110
n bits : 0 to 2^-1 8 1000
bits 10 11
Powers of Two
2° 2’ 22 23 z” 25 26 27 28 29 2
I 2 4 8 16 32 64 128 256 512 1024
21° Kilo = 1024 = 1 thousand
2″ Mega = 1,048,576 I 1 million
= 1 billion
24° Te ra a 1 trillion
238 bytes=
28.230=256
8 Octal : Base-8 (Digits : 0 to
828 8° 648¥
5 – is ” 53,0 = 65g
Notice that each of The
can be represented by 3 bits
001010- – — – – 110117
So w e immediatly
o u r octal
Hexadecimal
Deajalobjjajstlexgdeamo.tl
FD 141110 –
Digits o- q o- I O- F
16216 16° 53=3.16 + 5
-2 5 ¥ = 35 ,, = 0÷°l°g#
2-16-115= 2F
= 0010111 I
whycan we group 4bits to
hexadecimal
Consider :
10I1 0010011 I
I0I1OOOOO000
+ 00I00000
+ 0010 1- 0 111
shifted shifted u n shifted
(101 1)✗28 + (00/0)×2 + (0111)✗
✗1621-2✗16 -17
• The same reasoning applies for grouping 3 bits to form an octal #
• Pad MSB if e. g.
necessary .
( 11101072=-10011
1010)z_= 3A TT
= 8×1000-17×100 +0 ✗ 10 + 2×1
8702 = 8×103-17✗10 t0×10″ + 2✗10°
= 8000+700+0 +2
Digits: 0 . – -9 shift Left = ✗ 10
Max (n ɥ
=I✗16 8 ✗41×20×1
0×2>+1×2-+1×2 ‘
= 16+0 +4tzt0
shift Left
Max (n bits)
Base8_(octal)_
= 64 + 56 + 3
shiftLeft= ✗8
Max : 8^-1 318 ⇒ 310s
Baselbltlexadeg.im#
192+8+0=200
2^-6 = 2×16 + 10×16 + 6 ✗ 16°
= 512 1- 160 1- 6
shift left = ✗ 16
Digits : Max
F 14,6 20,0
⇒ 256+64=320,0
→ Binary conversion
(and a funny property of binary #
find Powers of 2 That sum to
27 z’ z’ z” z’ z’ z’ 2°
256 128 64 32 16 8 4 2 I
Representing negative
-5I1Ol} TT
But with 4 bits I c a n represent 24=16
v a lu e s
so one is wasted :
1- 0 0 0 0 0
Also I cant add
in the usual
One’s complement ( 4 bits )
Take Positive value And flip all bits .
5=>0101⇒1010
T w o representations of
0000″” “+”
0111 I ;ff⇒
o v e r f wl o w h y
Two ‘s – Complement Max
Pos # : standard
Neg # : start w/ magnitude in binary Flip Bits
0101 ⇒ 1010 ⇒ 1011
0000 ⇒ 11 I 1
: 2 01 I ⇒ 1100 ⇒ 1101
( a s expected)
4 01 00 ⇒ 1011 ⇒ 91%01 add I flip
⇐1110⇐ I ”
so we can do subtraction by
reusing addition circuitry which is much simpler !
1 converting 2’s Comp to
IsMSBa 0or a
conversion to
Convert to Positive
Convert to Decimal a s usual
c)Adda “- “signin
Example: I 1 1910
Flip and add 1 again!
flip 00 I 0 = 2 00 I 0 1-I
add sign ⇒ -2 ¥ -20
canweflipbitsandadd1 to
reverse the sign (pos → neg o r neg → pos) ?
Flipping bits (o → 1 , I → 0) is the
as subtracting from all 1s For example: 5. = 0101
+ 98¥Iadd-1-1
I n t w o ‘s complement 1 0 1 1 i s – 5
But w e also recognize 1011 a s 11,0 in standard binary
and 16- 5=11
So, in general then- bit 2s- complement of ✗ is –
and adding 1
– -11 – as
lX =2″✗(expected)
Process : =
2^-1 – (2^-11)+1
-I- 1-+= 2″2h✗I
Another way of looking at 2s- complement is to recognize that if we have
around in a
fixed # of bits , the numbers
: • 2N o.max.mn#T
overflow) (overflow )
⇒ neg neg +
return to numbers on a circle (instead
of a arithmetic
line ) when we discuss modular
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com