Introduction to Computer Systems 15-213/18-243, spring 2009 1st Lecture, Jan. 12th
Data representation I
Copyright By PowCoder代写加微信 assignmentchef
Acknowledgement: These slides are based on the textbook
(Computer Systems: A Programmer’s Perspective) and its slides.
What happens in a computer during program execution?
Our focus today:
“How is data stored in memory?”
#include
int main()
int c=a+b;
printf(“%d
”,c);
Background on bits
Representation: unsigned and signed
Conversion, casting
Addition, negation, multiplication, shifting
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Represent everything in bits
Each bit is 0 or 1
Bits are used to
Encode instructions (to be used in CPU)
Represent numbers, sets, strings, etc…
Base 2 number representation
Represent 1521310 as 111011011011012
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Encoding Byte Values
1 byte = 8 bits
Binary 000000002 to 111111112
Decimal: 010 to 25510
Hexadecimal 0016 to FF16
Base 16 number representation
Use characters ‘0’ to ‘9’ and ‘A’ to ‘F’
Write FA1D37B16 in C as
#include
int main() {
printf(“%x
”,262263675);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Example Data Representations
C Data TypeTypical 32-bitTypical 64-bitx86-64
char111
short222
long488
float444
double888
long double−−16
pointer488
We will study them in lecture 3
#include
int main() {
printf(“%d
”,sizeof(int));
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Boolean Algebra on Single Bit
Algebra of logic expression
Encode “True” as 1 and “False” as 0
A&B = 1 when both A=1 and B=1
A|B = 1 when either A=1 or B=1
~A = 1 when A=0
Exclusive-Or (Xor) ^
A^B = 1 when either A=1 or B=1, but not both
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Boolean Algebra on Bit Vectors
Operate on Bit Vectors
Operations applied bitwise
& 01010101
| 01010101
^ 01010101
~ 01010101
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Example: Representing & Manipulating Sets
Representation
Width w bit vector represents subsets of {0, …, w–1}
Examples of bit vectors:
Operations
X & YIntersection01000001{ 0, 6 }
X | YUnion01111101{ 0, 2, 3, 4, 5, 6 }
X ^ YSymmetric difference00111100{ 2, 3, 4, 5 }
~YComplement10101010{ 1, 3, 5, 7 }
Position76543210
Vector X01101001
Vector Y01010101
{ 0, 3, 5, 6 }
{ 0, 2, 4, 6 }
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Bit-Level Operations in C
Operations &,|,~,^ Available in C
Apply to any “integral” data type
long, int, short, char, unsigned
View arguments as bit vectors
Arguments applied bit-wise
Examples (char data type)
~0x41 0xBE
~010000012 101111102
~0x00 0xFF
~000000002 111111112
0x69 & 0x55 0x41
011010012 & 010101012 010000012
0x69 | 0x55 0x7D
011010012 | 010101012 011111012
#include
int main() {
char ch = 0x69 & 0x55;
printf(“%x
”,ch);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Contrast: Logic Operations in C
Contrast to Logical Operators
View 0 as “False”
View nonzero as “True”
Always return 0 or 1
Examples (char data type)
!0x41 0x00
!0x00 0x01
!!0x41 0x01
0x69 && 0x55 0x01
0x69 || 0x55 0x01
Watch out for && vs. & (and || vs. |)…
a common mistake in C programming
#include
int main() {
char ch = 0x69 && 0x55;
printf(“%x
”,ch);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Shift Operations
Left Shift: x << yShift bit-vector x left y positionsThrow away extra bits on leftFill with 0’s on rightRight Shift: x >> y
Shift bit-vector x right y positions
Throw away extra bits on right
Logical shift
Fill with 0’s on left
Arithmetic shift
Replicate most significant bit on left
Undefined Behavior
Shift amount < 0 or ≥ word sizeArgument xArgument xArith. >> 2
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Background on bits
Representation: unsigned and signed
Conversion, casting
Addition, negation, multiplication, shifting
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Encoding Integers
short int x =15213;
short int y = -15213;
C short: 2 bytes long
For 2’s complement, most significant bit indicates sign
0 for nonnegative
1 for negative
Two’s Complement
#include
int main() {
short int x =15213;
short int y = -15213;
printf(“%x %x
”,x,y);
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Numeric Ranges
Unsigned Values
UMax = 2w – 1
Two’s Complement Values
TMin= –2w–1
TMax = 2w–1 – 1
Other Values
Values for W = 16
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Values for Different Word Sizes
Observations
|TMin | = TMax + 1
Asymmetric range
UMax=2 * TMax + 1
C Programming
#include
Values platform specific
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsigned & Signed Numeric Values
Equivalence
Same encodings for nonnegative values
Uniqueness
Every bit pattern represents unique integer value
Each representable integer has unique bit encoding
Can Invert Mappings
U2B(x)=B2U-1(x)
Bit pattern for unsigned integer
T2B(x)=B2T-1(x)
Bit pattern for two’s comp integer
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Background on bits
Representation: unsigned and signed
Conversion, casting
Addition, negation, multiplication, shifting
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Two’s Complement
Maintain Same Bit Pattern
Mapping Between Signed & Unsigned
Two’s Complement
Maintain Same Bit Pattern
Mappings between unsigned and two’s complement numbers:
Keep bit representations and reinterpret
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Mapping Signed Unsigned
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Mapping Signed Unsigned
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
T Max+ 1
2’s Complement Range
Conversion Visualized
2’s Comp. Unsigned
Ordering Inversion
Negative Big Positive
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Signed vs. Unsigned in C
By default are considered to be signed integers
Unsigned if have “U” as suffix
0U, 4294967259U
Explicit casting between signed & unsigned same as U2T and T2U
int tx, ty;
unsigned ux, uy;
tx = (int) ux;
uy = (unsigned) ty;
Implicit casting also occurs via assignments and procedure calls
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
00U==unsigned
-10<signed-10U>unsigned
2147483647-2147483648 >signed
2147483647U-2147483648 <unsigned 2147483647 2147483648U <unsigned 2147483647 (int) 2147483648U>signed
Expression Evaluation
If there is a mix of unsigned and signed in single expression,
signed values implicitly cast to unsigned
Including comparison operations <, >, ==, <=, >=
Examples for W = 32:TMIN = -2147483648 , TMAX = 2147483647
Constant1Constant2RelationEvaluation
2147483647-2147483647-1
2147483647U-2147483647-1
2147483647 2147483648U
2147483647 (int) 2147483648U
Casting Surprises
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Background on bits
Representation: unsigned and signed
Conversion, casting
Addition, negation, multiplication, shifting
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsigned Addition
Standard Addition Function
Ignores carry output
Implements Modular Arithmetic
s= UAddw(u , v)=u + vmod 2w
True Sum: w+1 bits
Operands: w bits
Discard Carry: w bits
UAddw(u , v)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Two’s Complement Addition (for Signed)
TAdd and UAdd have Identical Bit-Level Behavior
Signed vs. unsigned addition in C:
int s, t, u, v;
s = (int) ((unsigned) u + (unsigned) v);
Will give s == t
True Sum: w+1 bits
Operands: w bits
Discard Carry: w bits
TAddw(u , v)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
TAdd Overflow
Functionality
True sum requires w+1 bits
Drop off MSB
Treat remaining bits as 2’s comp. integer
TAdd Result
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsigned Multiplication in C
Standard Multiplication Function
Ignores high order w bits
Implements Modular Arithmetic
UMultw(u , v)=u · vmod 2w
True Product: 2*wbits
Operands: w bits
Discard w bits: w bits
UMultw(u , v)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Signed Multiplication in C
Standard Multiplication Function
Ignores high order w bits
Some of which are different for signed vs. unsigned multiplication
Lower bits are the same
True Product: 2*wbits
Operands: w bits
Discard w bits: w bits
TMultw(u , v)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Power-of-2 Multiply with Shift
u << k gives u * 2kBoth signed and unsignedu << 3==u * 8(u << 5) – (u << 3)==u * 24Most machines shift and add faster than multiplyCompiler generates this code automaticallyTrue Product: w+kbitsOperands: w bitsDiscard kbits: w bitsUMultw(u , 2k)TMultw(u , 2k)Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third EditionUnsigned Power-of-2 Divide with ShiftQuotient of Unsigned by Power of 2u >> k gives u / 2k
Uses logical shift
u / 2k
Binary Point
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Unsigned vs. Signed
Understand the domain of types
Don’t use unsigned without understanding implications
Easy to make mistakes
unsigned i;
unsigned cnt=10;
for (i = cnt; i >= 0; i–)
printf(“%u %d
”,i,i);
OK to use unsigned to represent sets
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Background on bits
Representation: unsigned and signed
Conversion, casting
Addition, negation, multiplication, shifting
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Byte-Oriented Memory Organization
Programs refer to data by address
Conceptually, we view it as a very large array of bytes
An address is like an index into that array
and, a pointer variable stores an address
Note: system provides private address spaces to each “process”
Think of a process as a program being executed
So, a program can read/write its own data, but not others’ data
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Machine Words
Any given computer has a “Word Size”
Nominal size of integer-valued data
and of addresses
Until recently, most machines used 32 bits (4 bytes) as word size
Limits addresses to 4GB (232 bytes)
Increasingly, machines have 64-bit word size
Potentially, could use 18 EB (exabytes) of addressable memory
That’s 18.4 X 1018
Machines still support multiple data formats
Fractions or multiples of word size
Always integral number of bytes
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Word-Oriented Memory Organization
Addresses Specify Byte Locations
Address of first byte in word
Addresses of successive words differ by 4 (32-bit) or 8 (64-bit)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Byte Ordering
How are the bytes within a word ordered in memory?
Conventions
Big Endian: Sun, PPC Mac, Internet
Least significant byte has highest address
Little Endian: x86, ARM processors running Android, iOS, and Windows
Least significant byte has lowest address
Variable x has 4-byte value of 0x01234567
Address given by &x is 0x100
Big Endian
Little Endian
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Representing Integers
Decimal:15213
Binary:0011 1011 0110 1101
Hex:3B6D
IA32, x86-64
int A = 15213;
IA32, x86-64
Two’s complement representation
int B = -15213;
long int C = 15213;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
Examining Data Representations
Code to Print Byte Representation of Data
Casting pointer to unsigned char * allows treatment as a byte array
Printf directives:
%p:Print pointer
%x:Print Hexadecimal
typedef unsigned char *pointer;
void show_bytes(pointer start, size_t len){
for (i = 0; i < len; i++)printf(“%pt0x%.2x
“,start+i, start[i]);printf(”
“);Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Editionshow_bytes Execution Exampleint a = 15213;printf(“int a = 15213;
“);show_bytes((pointer) &a, sizeof(int));Result (Linux x86-64):int a = 15213;0x7fffb7f71dbc6d0x7fffb7f71dbd3b0x7fffb7f71dbe000x7fffb7f71dbf00Decimal:15213Binary:0011 1011 0110 1101Hex:3B6DBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third EditionRepresenting PointersDifferent compilers & machines assign different locations to objectsEven get different results each time run programint B = -15213;int *P = &BBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Editionchar S[6] = “18213”;Representing StringsStrings in CRepresented by array of charactersEach character encoded in ASCII formatStandard 7-bit encoding of character setCharacter “0” has code 0x30Digit ihas code 0x30+iString should be null-terminatedFinal character = 0CompatibilityByte ordering not an issueBryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition Decimal Hex Binary 3B 6D 00111011 01101101C4 93 11000100 10010011 00111011 0110110111000100 10010011 Decimal Hex Binary FF FF 11111111 111111117F FF 01111111 1111111180 00 10000000 00000000FF FF 11111111 1111111100 00 00000000 00000000 11111111 1111111101111111 1111111110000000 0000000011111111 1111111100000000 00000000 8 16 3264 UMax 255 65,535 4,294,967,295 18,446,744,073,709,551,615TMax 127 32,767 2,147,483,647 9,223,372,036,854,775,807TMin -128 -32,768 -2,147,483,648 -9,223,372,036,854,775,8084,294,967,29518,446,744,073,709,551,6152,147,483,6479,223,372,036,854,775,807-2,147,483,648-9,223,372,036,854,775,808 Division Computed Hex Binary 15213 15213 3B 6D 00111011 011011017606.5 7606 1D B6 00011101 10110110950.8125 950 03 B6 00000011 1011011059.4257813 59 00 3B 00000000 00111011 00111011 0110110100011101 1011011000000011 1011011059.425781300000000 00111011/docProps/thumbnail.jpeg程序代写 CS代考加微信: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.