Get 2 days of unlimited access
Class Notes (1,000,000)
US (420,000)
BU (8,000)
CAS CS (100)
Lecture 14

CAS CS 111 Lecture Notes - Lecture 14: Binary NumberPremium


Department
Computer Science
Course Code
CAS CS 111
Professor
David Sullivan
Lecture
14

This preview shows pages 1-3. to view the full 20 pages of the document.
Bits%and%Bytes
Everything%stored%in%a%computer%is%essentially%a%binary%number?
0110110010100111
§
Each%digit%in%a%binary%number%of%one%bit
A%single%0%or%1
§
Based%on%two%voltages:%"low"%=%0,%"high"%=%1
§
One%byte%is%8%bits
Example:%01101100
§
Bits%of%Data
A%given%set%of%bits%can%have%more%than%one%meaning
Representing%Integers%in%Decimal
In%base%10%(decimal),%each%column%represents%a%power%of%10.
What%Does%the%Rightmost%Bit%Tell% Us?
If%the%rightmost%bit%is%0,%the%number%is%even.
If%the%rightmost%bit%is%1,%the%number%is%odd
Binary%to%Decimal%(On%Paper)
Number%the%bits%from%right%to%left
§
For%each%bit%that%is%1,%add%2^n,%where%n%=%the%bit%number
§
Another%example:%What%is%the%integer%represented%by%1001011?
§
THERE%ARE%10%TYPES%OF%PEOPLE:%THOSE%WHO%UNDERSTAND%BINARY,%AND%
THOSE%WHO%DO%NOT%UNDERSTAND%IT.
Decimal%to%Binary%(On%Paper)
Go%in%the%reverse%direction:%determine%which%powers%of%2%need%to%be%
added%together%to%produce%the%decimal%number.
Start%with%the%largest%of%2%less%than%or%equal%to%the%number,%and%work%
down%from%there.
Example:%What%is%53%in%binary?
32%is%the%largest%power%of%2%<=%53
53%=%32%+%21
®
Now,%break%the%21%into%powers%of%2:
53%=%53%+%16%+%5
®
Now,%break%the%5%into%powers%of%2:
53%=%32%+%16%+%4%+%1
®
1%is%a%power%of%2%(2^0)%so%we're%done:
53%=%32%+%16%+%4%+%1%=%(2^5)%+%(2^4)%+%(2^3)%+%(2^2)%+%
(2^0)%=%110101
®
§
Which%of%these%is%a%correct%partial%binary%representation%of%the%decimal%
integer%90?
A%Binary%Address!
Another%Coincidence?
Shifting%Bits%to%the%Left
A%left-shift:
Moves%every%bit%of%a%binary%number%to%the%left
§
Adds%a%0%in%the%right-most%place
§
For%example:
A%left-shift%by%1%gives
§
§
Left-shifting%by%1%doubles%the%value%of%a%number.
In%Python%we%can%apply%the%left-shift%(<<)%to%any%integer:
§
Recall:%Decimal% to%Binary%(On%Paper)
This%is%a%left-to-right%conversion.
We%begin%by%determining%the%leftmost%digit
§
The%first%step%is%tricky%to%perform%computationally,%because%we%need%to%
determine%the%largest%power.
Decimal%to%Binary:%Right-to-Left
We%can%use%a%right-to-left%approach%instead.
For%example:%Let's%convert%139%to%binary:
To%convert%139:%recursively%convert%69,%then%put%a%1%at%the%end!
dec_to_bin()%Function
dec_to_bin(n)
Takes%an%integer%n
§
Should%return%a%string%representation%of%n's%binary%representation
§
How%dec_to_bin()%Should%Work
Binary%to%Decimal:%Right-to%-Left
Here%again,%we%can%use%a%right-to-left%approach.
For%example:
§
Binary%to%Decimal:%Right-to-Left
Here%again,%we%can%use%a%right-to-left%approach
For%example:
§
To%convert%'1101':
Recursively%covert%"110"
§
Double%the%result
§
Add%1%for%the%rightmost%bit
§
How%to%bin_to_dec()%-Should%Work…
Binary%Addition%Fundamentals
Adding%Decimal%Numbers
Add%these%two%binary%numbers%WITHOUT%converting%to%decimal!
It's%All%Bits!
Another%example:%text
§
All%type%of%data%are%represented%binary.
§Images,%sounds,%movies,%floating-point%numbers,%etc
All%computation%involves%manipulating%bits!
Friday's)Lecture
Saturday,%6%October%2018
9:53%PM

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Subscribers Only
Bits%and%Bytes
Everything%stored%in%a%computer%is%essentially%a%binary%number?
0110110010100111
§
Each%digit%in%a%binary%number%of%one%bit
A%single%0%or%1
§
Based%on%two%voltages:%"low"%=%0,%"high"%=%1
§
One%byte%is%8%bits
Example:%01101100
§
Bits%of%Data
A%given%set%of%bits%can%have%more%than%one%meaning
Representing%Integers%in%Decimal
In%base%10%(decimal),%each%column%represents%a%power%of%10.
What%Does%the%Rightmost%Bit%Tell% Us?
If%the%rightmost%bit%is%0,%the%number%is%even.
If%the%rightmost%bit%is%1,%the%number%is%odd
Binary%to%Decimal%(On%Paper)
Number%the%bits%from%right%to%left
§
For%each%bit%that%is%1,%add%2^n,%where%n%=%the%bit%number
§
Another%example:%What%is%the%integer%represented%by%1001011?
§
THERE%ARE%10%TYPES%OF%PEOPLE:%THOSE%WHO%UNDERSTAND%BINARY,%AND%
THOSE%WHO%DO%NOT%UNDERSTAND%IT.
Decimal%to%Binary%(On%Paper)
Go%in%the%reverse%direction:%determine%which%powers%of%2%need%to%be%
added%together%to%produce%the%decimal%number.
Start%with%the%largest%of%2%less%than%or%equal%to%the%number,%and%work%
down%from%there.
Example:%What%is%53%in%binary?
32%is%the%largest%power%of%2%<=%53
53%=%32%+%21
®
Now,%break%the%21%into%powers%of%2:
53%=%53%+%16%+%5
®
Now,%break%the%5%into%powers%of%2:
53%=%32%+%16%+%4%+%1
®
1%is%a%power%of%2%(2^0)%so%we're%done:
53%=%32%+%16%+%4%+%1%=%(2^5)%+%(2^4)%+%(2^3)%+%(2^2)%+%
(2^0)%=%110101
®
§
Which%of%these%is%a%correct%partial%binary%representation%of%the%decimal%
integer%90?
A%Binary%Address!
Another%Coincidence?
Shifting%Bits%to%the%Left
A%left-shift:
Moves%every%bit%of%a%binary%number%to%the%left
§
Adds%a%0%in%the%right-most%place
§
For%example:
A%left-shift%by%1%gives
§
§
Left-shifting%by%1%doubles%the%value%of%a%number.
In%Python%we%can%apply%the%left-shift%(<<)%to%any%integer:
§
Recall:%Decimal% to%Binary%(On%Paper)
This%is%a%left-to-right%conversion.
We%begin%by%determining%the%leftmost%digit
§
The%first%step%is%tricky%to%perform%computationally,%because%we%need%to%
determine%the%largest%power.
Decimal%to%Binary:%Right-to-Left
We%can%use%a%right-to-left%approach%instead.
For%example:%Let's%convert%139%to%binary:
To%convert%139:%recursively%convert%69,%then%put%a%1%at%the%end!
dec_to_bin()%Function
dec_to_bin(n)
Takes%an%integer%n
§
Should%return%a%string%representation%of%n's%binary%representation
§
How%dec_to_bin()%Should%Work
Binary%to%Decimal:%Right-to%-Left
Here%again,%we%can%use%a%right-to-left%approach.
For%example:
§
Binary%to%Decimal:%Right-to-Left
Here%again,%we%can%use%a%right-to-left%approach
For%example:
§
To%convert%'1101':
Recursively%covert%"110"
§
Double%the%result
§
Add%1%for%the%rightmost%bit
§
How%to%bin_to_dec()%-Should%Work…
Binary%Addition%Fundamentals
Adding%Decimal%Numbers
Add%these%two%binary%numbers%WITHOUT%converting%to%decimal!
It's%All%Bits!
Another%example:%text
§
All%type%of%data%are%represented%binary.
§Images,%sounds,%movies,%floating-point%numbers,%etc
All%computation%involves%manipulating%bits!
Friday's)Lecture
Saturday,%6%October%2018 9:53%PM

Only pages 1-3 are available for preview. Some parts have been intentionally blurred.

Subscribers Only
Bits%and%Bytes
Everything%stored%in%a%computer%is%essentially%a%binary%number?
0110110010100111
§
Each%digit%in%a%binary%number%of%one%bit
A%single%0%or%1
§
Based%on%two%voltages:%"low"%=%0,%"high"%=%1
§
One%byte%is%8%bits
Example:%01101100
§
Bits%of%Data
A%given%set%of%bits%can%have%more%than%one%meaning
Representing%Integers%in%Decimal
In%base%10%(decimal),%each%column%represents%a%power%of%10.
What%Does%the%Rightmost%Bit%Tell% Us?
If%the%rightmost%bit%is%0,%the%number%is%even.
If%the%rightmost%bit%is%1,%the%number%is%odd
Binary%to%Decimal%(On%Paper)
Number%the%bits%from%right%to%left
§
For%each%bit%that%is%1,%add%2^n,%where%n%=%the%bit%number
§
Another%example:%What%is%the%integer%represented%by%1001011?
§
THERE%ARE%10%TYPES%OF%PEOPLE:%THOSE%WHO%UNDERSTAND%BINARY,%AND%
THOSE%WHO%DO%NOT%UNDERSTAND%IT.
Decimal%to%Binary%(On%Paper)
Go%in%the%reverse%direction:%determine%which%powers%of%2%need%to%be%
added%together%to%produce%the%decimal%number.
Start%with%the%largest%of%2%less%than%or%equal%to%the%number,%and%work%
down%from%there.
Example:%What%is%53%in%binary?
32%is%the%largest%power%of%2%<=%53
53%=%32%+%21
®
Now,%break%the%21%into%powers%of%2:
53%=%53%+%16%+%5
®
Now,%break%the%5%into%powers%of%2:
53%=%32%+%16%+%4%+%1
®
1%is%a%power%of%2%(2^0)%so%we're%done:
53%=%32%+%16%+%4%+%1%=%(2^5)%+%(2^4)%+%(2^3)%+%(2^2)%+%
(2^0)%=%110101
®
§
Which%of%these%is%a%correct%partial%binary%representation%of%the%decimal%
integer%90?
A%Binary%Address!
Another%Coincidence?
Shifting%Bits%to%the%Left
A%left-shift:
Moves%every%bit%of%a%binary%number%to%the%left
§
Adds%a%0%in%the%right-most%place
§
For%example:
A%left-shift%by%1%gives
§
§
Left-shifting%by%1%doubles%the%value%of%a%number.
In%Python%we%can%apply%the%left-shift%(<<)%to%any%integer:
§
Recall:%Decimal% to%Binary%(On%Paper)
This%is%a%left-to-right%conversion.
We%begin%by%determining%the%leftmost%digit
§
The%first%step%is%tricky%to%perform%computationally,%because%we%need%to%
determine%the%largest%power.
Decimal%to%Binary:%Right-to-Left
We%can%use%a%right-to-left%approach%instead.
For%example:%Let's%convert%139%to%binary:
To%convert%139:%recursively%convert%69,%then%put%a%1%at%the%end!
dec_to_bin()%Function
dec_to_bin(n)
Takes%an%integer%n
§
Should%return%a%string%representation%of%n's%binary%representation
§
How%dec_to_bin()%Should%Work
Binary%to%Decimal:%Right-to%-Left
Here%again,%we%can%use%a%right-to-left%approach.
For%example:
§
Binary%to%Decimal:%Right-to-Left
Here%again,%we%can%use%a%right-to-left%approach
For%example:
§
To%convert%'1101':
Recursively%covert%"110"
§
Double%the%result
§
Add%1%for%the%rightmost%bit
§
How%to%bin_to_dec()%-Should%Work…
Binary%Addition%Fundamentals
Adding%Decimal%Numbers
Add%these%two%binary%numbers%WITHOUT%converting%to%decimal!
It's%All%Bits!
Another%example:%text
§
All%type%of%data%are%represented%binary.
§Images,%sounds,%movies,%floating-point%numbers,%etc
All%computation%involves%manipulating%bits!
Friday's)Lecture
Saturday,%6%October%2018 9:53%PM
You're Reading a Preview

Unlock to view full version

Subscribers Only