Carnegie Mellon
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1
Carnegie Mellon
Bits, Bytes, and Integers – Part 2
15-213: Introduction to Computer Systems 3rd Lecture, May 21, 2020
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
2
Carnegie Mellon
Assignment Announcements
Lab 0 available via Autolab. ▪ Due Fri, May 29, 11:00pm
▪ No grace days
▪ No late submissions ▪ Just do it!
Lab 1 will be available via Autolab
▪ Release on evening of Fri, May 22
▪ Due Fri, May 29, 11:59pm
▪ Read instructions carefully: writeup, bits.c, tests.c
▪ Quirky software infrastructure
▪ Based on lectures 2, 3, and 4 (CS:APP Chapter 2)
▪ After today’s lecture you will know everything for the integer problems
▪ Floating point covered Fri, May 22 Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
3
Carnegie Mellon
Summary From Last Lecture
Representing information as bits
Bit-level manipulations
Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting
Representations in memory, pointers, strings Summary
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
4
Carnegie Mellon
Encoding Integers Unsigned w−1
B2U(X) = xi2i i=0
Two’s Complement w−2 B2T(X) = −xw−12w−1+xi2i
i=0
Two’s Complement Examples (w = 5)
10 =
-10 =
8+2 = 10
-16+4+2 = -10
Sign Bit
-16
8
4
2
1
0
1
0
1
0
-16
8
4
2
1
1
0
1
1
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
5
Carnegie Mellon
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
X
B2U(X) B2T(X)
0000
00
0001
11
0010
22
0011
33
0100
44
0101
55
0110
66
0111
77
1000
8 –8
1001
9 –7
1010
10 –6
1011
11 –5
1100
12 –4
1101
13 –3
1110
14 –2
1111
15 –1
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
6
Expression containing signed
and unsigned int:
int is cast to unsigned
Carnegie Mellon
Sign Extension and Truncation Sign Extension
Truncation
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
7
Carnegie Mellon
Misunderstanding integers can lead to the end of the world as we know it!
Thule (Qaanaaq), Greenland
US DoD “Site J” Ballistic Missile Early Warning System (BMEWS)
10/5/60: world nearly ends
Missile radar echo: 1/8s
BMEWS reports: 75s echo(!)
1000s of objects reported
NORAD alert level 5:
▪ Immediate incoming nuclear attack!!!!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
8
Carnegie Mellon
Kruschev was in NYC 10/5/60 (weird time to attack) ▪ someone in Qaanaaq said “why not go check outside?”
“Missiles” were actually THE MOON RISING OVER NORWAY
Expected max distance: 3000 mi; Moon distance: .25M miles! .25M miles % sizeof(distance) = 2200mi.
Overflow of distance nearly caused nuclear apocalypse!! Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
9
Carnegie Mellon
Today: Bits, Bytes, and Integers
Representing information as bits
Bit-level manipulations
Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting
Representations in memory, pointers, strings Summary
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
10
Unsigned Addition
Operands: w bits True Sum: w+1 bits
u +v
u+v UAddw(u , v)
0
1
Carnegie Mellon
•••
•••
•••
•••
Discard Carry: w bits
Standard Addition Function
0000
▪ Ignores carry output
Implements Modular Arithmetic
s = UAddw(u,v) = u+v mod2w
1
2
unsigned char
1110 1001 E9 223 + 11010101 +D5 +213
8
2
3
3
0001
0010
0011
4
4
0100
5
7
5
6
6
7
0101
0110
0111
8
9
9
A
10
1000
1001
1010
B
11
1011
C
12
D
13
1100
E
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
11
F
0
14
15
1101
1110
1111
Unsigned Addition
Operands: w bits True Sum: w+1 bits
u +v
u+v UAddw(u , v)
0
1
Carnegie Mellon
•••
•••
•••
•••
Discard Carry: w bits
Standard Addition Function
0000
▪ Ignores carry output
Implements Modular Arithmetic
s = UAddw(u,v) = u+v mod2w
1
2
unsigned char
1110 1001 E9 223 + 11010101 +D5 +213
1 1011 1110 1BE 446 1011 1110 BE 190
8
2
3
3
0001
0010
0011
4
4
0100
5
7
5
6
6
7
0101
0110
0111
8
9
9
A
10
1000
1001
1010
B
11
1011
C
12
D
13
1100
E
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
12
F
0
14
15
1101
1110
1111
Carnegie Mellon
Visualizing (Mathematical) Integer Addition
Add4(u , v)
Integer Addition
▪ 4-bit integers u, v
▪ Compute true sum Add4(u , v)
▪ Values increase linearly with u and v
▪ Forms planar surface
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
13
Integer Addition
32 28 24
20 16 12
14
12
10 8
8 46v
0
0
4
22
u4
6
8 10 12 14
0
Carnegie Mellon
Visualizing Unsigned Addition
Wraps Around ▪ If true sum ≥ 2w ▪ At most once
True Sum
2w+1
Overflow
2w 0
Overflow
14 6 12
10 8v
6 4
Modular Sum
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
14
UAdd4(u , v)
16 14 12
10 8
4 2 0
0
u
246 2
8 10 12
0
14
Carnegie Mellon
Two’s Complement Addition
Operands: w bits u
•••
+v u+v
•••
True Sum: w+1 bits
Discard Carry: w bits TAddw(u , v)
•••
•••
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); t =u+v
▪Willgive s==t
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1110 1001 E9 -23 + 11010101 +D5 +-43
1 1011 1110 1BE -66 1011 1110 BE -66
15
Carnegie Mellon
TAdd Overflow Functionality
▪ True sum requires w+1 bits
▪ Drop off MSB
▪ Treat remaining bits as
2’s comp. integer
True Sum
0 111…1 0 100…0 0 000…0 1 011…1 1 000…0
2w–1 2w –1–1
0
–2w –1 –2w
PosOver
TAdd Result
011…1 000…0 100…0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
16
NegOver
Carnegie Mellon
Visualizing 2’s Complement Addition NegOver
Values
▪ 4-bit two’s comp.
▪ Range from -8 to +7
Wraps Around ▪ If sum 2w–1
▪ Becomes negative
▪ At most once ▪ If sum < –2w–1
▪ Becomes positive ▪ At most once
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
17
8 6 4
2 0
TAdd4(u , v)
6 -2 4
-4 -6 -8
-8 -6 -4 -2
u
-6
2 0
-2
-4 v
024 -8 6
PosOver
Carnegie Mellon
Characterizing TAdd
Functionality
▪ True sum requires w+1 bits
Positive Overflow
▪ Drop off MSB
▪ Treat remaining bits as 2’s
comp. integer
TAdd(u , v) >0
v
<0
TAddw(u,v) =
2w
u+v TMinw u+vTMaxw
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
18
<0 u >0 Negative Overflow
w−1
u + v + 2 w u + v TMin (NegOver)
w−1
u+v−22w TMaxw u+v (PosOver)
Carnegie Mellon
Multiplication
Goal: Computing Product of w-bit numbers x, y
▪ Either signed or unsigned
But, exact results can be bigger than w bits ▪ Unsigned: up to 2w bits
▪ Result range: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1 ▪ Two’s complement min (negative): Up to 2w-1 bits
▪ Result range: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1
▪ Two’s complement max (positive): Up to 2w bits, but only for (TMinw)2
▪ Result range: x * y ≤ (–2w–1) 2 = 22w–2
So, maintaining exact results…
▪ would need to keep expanding word size with each product computed ▪ is done in software, if needed
▪ e.g., by “arbitrary precision” arithmetic packages Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
19
Carnegie Mellon
Unsigned Multiplication in C
•••
u *v
UMultw(u , v) Standard Multiplication Function
▪ Ignores high order w bits
Implements Modular Arithmetic
Operands: w bits
True Product: 2*w bits u · v
•••
•••
•••
•••
Discard w bits: w bits
UMultw(u , v)=
u · v mod 2w
1110 1001
* 11010101 * D5 * 213
1100 0001 1101 1101 C1DD 47499
1101 1101 DD 221
E9 223
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
20
Carnegie Mellon
Signed Multiplication in C
Operands: w bits
True Product: 2*w bits u · v
Discard w bits: w bits
•••
u *v
TMultw(u , v)
•••
•••
•••
•••
Standard Multiplication Function
▪ Ignores high order w bits
▪ Some of which are different for signed vs. unsigned multiplication
▪ Lower bits are the same
1110 1001
* 11010101 * D5 * -43
0000 0011 1101 1101 03DD 989
E9 -23
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
1101 1101 DD -35
21
Carnegie Mellon
Power-of-2 Multiply with Shift
Operation
▪u << kgivesu * 2k
▪ Both signed and unsigned
k
•••
Operands: w bits
True Product: w+k bits
Discard k bits: w bits
Examples ▪u<<3
u * 2k
u · 2k
TMultw(u , 2k)
0
•••
0
1
0
•••
0
0
•••
0
•••
0
0
== u*8 ▪(u<<5)–(u<<3)== u*24
▪ Most machines shift and add faster than multiply ▪ Compiler generates this code automatically
UMultw(u , 2k)
•••
0
•••
0
0
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
22
Important Lession: Trust Your Compiler!
Carnegie Mellon
Multiplication
Goal: Computing Product of w-bit numbers x, y
▪ Either signed or unsigned
But, exact results can be bigger than w bits ▪ Unsigned: up to 2w bits
▪ Result range: 0 ≤ x * y ≤ (2w – 1) 2 = 22w – 2w+1 + 1 ▪ Two’s complement min (negative): Up to 2w-1 bits
▪ Result range: x * y ≥ (–2w–1)*(2w–1–1) = –22w–2 + 2w–1
▪ Two’s complement max (positive): Up to 2w bits, but only for (TMinw)2
▪ Result range: x * y ≤ (–2w–1) 2 = 22w–2
So, maintaining exact results...
▪ would need to keep expanding word size with each product computed ▪ is done in software, if needed
▪ e.g., by “arbitrary precision” arithmetic packages Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
23
Carnegie Mellon
Unsigned Power-of-2 Divide with Shift
Quotient of Unsigned by Power of 2 ▪ u >> k gives u / 2k
▪ Uses logical shift
•••
•••
u / 2k
u / 2k u / 2k
k
Operands: Division:
Result:
Binary Point
0
•••
0
1
0
•••
0
0
0
•••
0
0
•••
.
•••
0
•••
0
0
•••
Division
Computed
Hex
Binary
x
15213
15213
3B 6D
00111011 01101101
x >> 1
7606.5
7606
1D B6
00011101 10110110
x >> 4
950.8125
950
03 B6
00000011 10110110
x >> 8
59.4257813
59
00 3B
00000000 00111011
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
24
Carnegie Mellon
Signed Power-of-2 Divide with Shift
Quotient of Signed by Power of 2 ▪ x >> k gives x / 2k
▪ Uses arithmetic shift
▪ Rounds wrong direction when u < 0 k
•••
•••
Operands: Division:
Result:
x / 2k
x / 2k RoundDown(x / 2k)
Binary Point .
0
•••
0
1
0
•••
0
0
0
•••
•••
0
•••
•••
Division
Computed
Hex
Binary
y
-15213
-15213
C4 93
11000100 10010011
y >> 1
-7606.5
-7607
E2 49
11100010 01001001
y >> 4
-950.8125
-951
FC 49
11111100 01001001
y >> 8
-59.4257813
-60
FF C4
11111111 11000100
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
25
•••
Carnegie Mellon
Correct Power-of-2 Divide
Quotient of Negative Number by Power of 2 ▪ Want x / 2k (Round Toward 0)
▪ Compute as (x+2k-1)/ 2k
▪ In C: (x + (1<
Case 1: No rounding
Dividend: Divisor:
k
1
•••
0
•••
0
0
u
+2k –1 / 2k
Binary Point
0
•••
0
0
1
•••
1
1
1
•••
1
•••
1
1
0
•••
0
1
0
•••
0
0
u/2k .
01
•••
1
1
1
•••
1
•••
1
1
Biasing has no effect
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
26
Carnegie Mellon
Correct Power-of-2 Divide (Cont.)
Case 2: Rounding
Dividend:
k +2k –1
Incremented by 1
/ 2k
x/2k .
1
•••
•••
x
0
•••
0
0
1
•••
1
1
1
•••
•••
Binary Point
0
•••
0
1
0
•••
0
0
Divisor:
01
•••
1
1
1
•••
•••
Biasing adds 1 to final result
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
27
Incremented by 1
Carnegie Mellon
Negation: Complement & Increment Negate through complement and increase
~x + 1 == -x
Example
▪ Observation: ~x + x == 1111…111 == -1
1
0
0
1
1
1
0
1
x + ~x
-1
0
1
1
0
0
0
1
0
1
1
1
1
1
1
1
1
x = 15213
Decimal
Hex
Binary
x
15213
3B 6D
00111011 01101101
~x
-15214
C4 92
11000100 10010010
~x+1
-15213
C4 93
11000100 10010011
y
-15213
C4 93
11000100 10010011
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
28
Carnegie Mellon
Complement & Increment Examples x= 0
Decimal
Hex
Binary
0
0
00 00
00000000 00000000
~0
-1
FF FF
11111111 11111111
~0+1
0
00 00
00000000 00000000
x = TMin
Decimal
Hex
Binary
x
-32768
80 00
10000000 00000000
~x
32767
7F FF
01111111 11111111
~x+1
-32768
80 00
10000000 00000000
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
29
Canonical counter example
Carnegie Mellon
Today: Bits, Bytes, and Integers
Representing information as bits
Bit-level manipulations
Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting ▪ Summary
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
30
Carnegie Mellon
Arithmetic: Basic Rules Addition:
▪ Unsigned/signed: Normal addition followed by truncate, same operation on bit level
▪ Unsigned: addition mod 2w
▪ Mathematical addition + possible subtraction of 2w
▪ Signed: modified addition mod 2w (result in proper range)
▪ Mathematical addition + possible addition or subtraction of 2w
Multiplication:
▪ Unsigned/signed: Normal multiplication followed by truncate,
same operation on bit level
▪ Unsigned: multiplication mod 2w
▪ Signed: modified multiplication mod 2w (result in proper range)
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
31
Carnegie Mellon
Why Should I Use Unsigned?
Don’t use without understanding implications
▪ Easy to make mistakes unsigned i;
for (i = cnt-2; i >= 0; i–) a[i] += a[i+1];
▪ Can be very subtle
#define DELTA sizeof(int)
int i;
for (i = CNT; i-DELTA >= 0; i-= DELTA)
…
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
32
Carnegie Mellon
Counting Down with Unsigned
Proper way to use unsigned as loop index unsigned i;
for (i = cnt-2; i < cnt; i--)
a[i] += a[i+1];
See Robert Seacord, Secure Coding in C and C++
▪ C Standard guarantees that unsigned addition will behave like modular
arithmetic
▪ 0 – 1→UMax
Even better size_t i;
for (i = cnt-2; i < cnt; i--)
a[i] += a[i+1];
▪ Data type size_t defined as unsigned value with length = word size Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
33
Carnegie Mellon
Why Should I Use Unsigned? (cont.) Do Use When Performing Modular Arithmetic
▪ Multiprecision arithmetic
Do Use When Using Bits to Represent Sets
▪ Logical right shift, no sign extension Do Use In System Programming
▪ Bit masks, device commands,...
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
34
Carnegie Mellon
Quiz Time!
Check out:
https://canvas.cmu.edu/courses/16836
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
35
Carnegie Mellon
Today: Bits, Bytes, and Integers
Representing information as bits
Bit-level manipulations
Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting ▪ Summary
Representations in memory, pointers, strings
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
36
Carnegie Mellon
Byte-Oriented Memory Organization
•••
Programs refer to data by address
▪ Conceptually, envision it as a very large array of bytes
▪ In reality, it’s not, but can think of it that way ▪ 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 clobber its own data, but not that of others
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
37
Carnegie Mellon
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 have 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
38
Carnegie Mellon
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)
32-bit 64-bit
Bytes Addr.
0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
Words
Words
Addr =
0000 ??
Addr =
0004 ??
Addr =
0008 ??
Addr =
0012 ??
Addr =
0000 ??
Addr =
0008 ??
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
39
Carnegie Mellon
Example Data Representations
C Data Type
Typical 32-bit
Typical 64-bit
x86-64
char
1
1
1
short
2
2
2
int
4
4
4
long
4
8
8
float
4
4
4
double
8
8
8
pointer
4
8
8
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
40
Carnegie Mellon
Byte Ordering
So, how are the bytes within a multi-byte word ordered in memory?
Conventions
▪ Big Endian: Sun (Oracle SPARC), PPC Mac, Internet
▪ Least significant byte has highest address
▪ Little Endian: x86, ARM processors running Android, iOS, and Linux
▪ Least significant byte has lowest address
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
41
Carnegie Mellon
Byte Ordering Example
Example
▪ Variable x has 4-byte value of 0x01234567 ▪ Address given by &x is 0x100
Big Endian Little Endian
0x100 0x101 0x102 0x103
0x100 0x101 0x102 0x103
01
23
45
67
67
45
23
01
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
42
Carnegie Mellon
Representing Integers
int A = 15213;
long int C = 15213;
IA32, x86-64 Sun
IA32 x86-64 Sun
6D
3B
00
00
00
00
3B
6D
6D
3B
00
00
6D
3B
00
00
00
00
00
00
00
00
3B
6D
int B = -15213;
IA32, x86-64 Sun
93
C4
FF
FF
FF
FF
C4
93
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
43
Decimal: 15213
Binary: 0011 1011 0110 1101 Hex: 3B6D
Two’s complement representation
Increasing addresses
Carnegie Mellon
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){
size_t i;
for (i = 0; i < len; i++)
printf(”%p\t0x%.2x\n",start+i, start[i]); printf("\n");
}
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
44
Carnegie Mellon
show_bytes Execution Example
int a = 15213;
printf("int a = 15213;\n"); show_bytes((pointer) &a, sizeof(int));
Result (Linux x86-64):
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
45
int a = 15213; 0x7fffb7f71dbc 6d 0x7fffb7f71dbd 3b 0x7fffb7f71dbe 00 0x7fffb7f71dbf 00
Carnegie Mellon
Representing Pointers
Sun IA32 x86-64
int B = -15213;
int *P = &B;
EF
FF
FB
2C
AC
28
F5
FF
3C
1B
FE
82
FD
7F
00
00
Different compilers & machines assign different locations to objects
Even get different results each time run program
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
46
Carnegie Mellon
Representing Strings
Strings in C
▪ Represented by array of characters
▪ Each character encoded in ASCII format
▪ Standard 7-bit encoding of character set ▪ Character “0” has code 0x30
– Digit i has code 0x30+I ▪ man ascii for code table
▪ String should be null-terminated ▪ Final character = 0
Compatibility
▪ Byte ordering not an issue
char S[6] = "18213";
IA32 Sun
31
38
32
31
33
00
31
38
32
31
33
00
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
47
Carnegie Mellon
Reading Byte-Reversed Listings
Disassembly
▪ Text representation of binary machine code
▪ Generated by program that reads the machine code
Example Fragment
Address Instruction Code
8048365: 5b
8048366: 81 c3 ab 12 00 00 804836c: 83 bb 28 00 00 00 00
Assembly Rendition
pop %ebx
add $0x12ab,%ebx
cmpl $0x0,0x28(%ebx)
Deciphering Numbers ▪ Value:
▪ Pad to 32 bits: ▪ Split into bytes: ▪ Reverse:
0x12ab 0x000012ab 00 00 12 ab ab 12 00 00
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
48
Carnegie Mellon
Summary
Representing information as bits
Bit-level manipulations
Integers
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting
Representations in memory, pointers, strings Summary
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
49
Carnegie Mellon
Integer C Puzzles
Initialization
x<0 ((x*2)<0) ux >= 0
x&7==7 (x<<30)<0 ux > -1
x>y -x<-y x * x >= 0
x>0&&y>0 x+y>0 x>=0 -x<=0 x<=0 -x>=0 (x|-x)>>31 == -1
ux >> 3 == ux/8 x >> 3 == x/8 x & (x-1) != 0
int x = foo(); int y = bar(); unsigned ux = x; unsigned uy = y;
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition
50