CSCI2467: Systems Programming Concepts
Slideset 2: Information as Data (CS:APP Chap. 2)
Instructor: M. Toups
Spring 2019
Course notes Preview Bits and Bytes Up next: Integer Values
Course updates
datalab out today! Will be more challenging and time consuming Due in slightly less than two weeks (Sunday Feb 10)
make sure AutoLab works for you (both Intro Lab and Data Lab) slides and resources available at http://2467.cs.uno.edu
Course notes Preview Bits and Bytes Up next: Integer Values
Handing in (introlab)
Autolab website
upload
download
Your computer
ssh
systems − lab
Course notes Preview Bits and Bytes Up next: Integer Values
Handing in (simpler)
Autolab website
download /upload
systems − lab
Course notes Preview Bits and Bytes Up next: Integer Values
Handing in (using scp)
Autolab website
download /upload
Your computer ssh/scp systems − lab
Course notes Preview Bits and Bytes Up next: Integer Values
CSCI Help Desk
Course notes Preview Bits and Bytes Up next: Integer Values
ints are not Integers
Source: xkcd.com
Z is infinitely large, computer memory is not. This is the fundamental challenge!
Course notes Preview Bits and Bytes Up next: Integer Values
ints are not Integers and floats are not Reals
Is x2 ≥ 0?
– Floating point? Yes!
– Int?
40000 ∗ 40000 → 1600000000 50000 ∗ 50000 →??
Is (x + y) + z = x + (y + z) ?
– Int (signed or unsigned): Yes!
– Float?
3.2 + (1e20 − 1e20) → 3.2 (3.2 + 1e20) − 1e20 →??
Course notes Preview Bits and Bytes Up next: Integer Values
Computer Arithmetic
Does not generate random values
– Arithmetic operations have important mathematical properties
Cannot assume all “usual” mathematical properties
– Due to finiteness of representations
– int operations satisfy ring properties:
Commutativity, associativity, distributivity
– Floating point operations satisfy ordering properties:
Monotonicity, values of signs
Observation
– Need to understand which abstractions apply in which contexts
– Important issues for compiler writers and serious application programmers
Course notes Preview Bits and Bytes Up next: Integer Values
Overview
Course notes 1 Preview
2 Bits and Bytes
Representing information as bits
Bit-level manipulations
Boolean Algebra Logical operators Shift operators
3 Up next: Integer Values Signed and Unsigned ints
Course notes Preview Bits and Bytes Up next: Integer Values
Everything is bits
00100011 01100100 01100100 00001010 01101101 00001010 00100000 01100110 01101100 01110010 00101001 00100000 01101110 00001010
01101001 01101110 01100011 01101100 01110101 01100101 00100000 00111100 01110011 01110100 01101001 01101111 00101110 01101000 00111110 00001010 01101001 01101110 01110100 00100000 01100001 01101001 01101110 00101000 00101001 01111011 00001010 00100000 00100000 00100000 01110000 01110010 01101001 01101110 01110100 00101000 00100010 01101000 01100101 01101100 01101111 00101100 00100000 01110111 01101111 01101100 01100100 01011100 01101110 00100010 00111011 00001010 00100000 00100000 00100000 01110010 01100101 01110100 01110101 01110010 00100000 00110000 00111011 00001010 01111101
#inclu de
print f(“hel lo, wo rld\n” );.
retur n 0;.} .
Each bit is 0 or 1
By encoding/interpreting sets of bits in various ways computers determine what to do (instructions) and represent and manipulate numbers, sets, strings, etc
Course notes Preview Bits and Bytes Up next: Integer Values
Everything is bits
Each bit is 0 or 1
By encoding/interpreting sets of bits in various ways computers determine what to do (instructions) and represent and manipulate numbers, sets, strings, etc
001000110110100101101110011000110110110001110101 011001000110010100100000001111000111001101110100 011001000110100101101111001011100110100000111110 000010100000101001101001011011100111010000100000 011011010110000101101001011011100010100000101001 000010100111101100001010001000000010000000100000 001000000111000001110010011010010110111001110100 011001100010100000100010011010000110010101101100 011011000110111100101100001000000111011101101111 011100100110110001100100010111000110111000100010 001010010011101100001010001000000010000000100000 001000000111001001100101011101000111010101110010 011011100010000000110000001110110000101001111101 00001010
#inclu de
print f(“hel lo, wo rld\n” );.
retur n 0;.} .
Course notes Preview Bits and Bytes Up next: Integer Values
Why bits?
Course notes Preview Bits and Bytes Up next: Integer Values
ENIAC
Course notes Preview Bits and Bytes Up next: Integer Values
Why bits?
Course notes Preview Bits and Bytes Up next: Integer Values
Why bits?
Electronic Implementation
Easy to store with bistable elements
Reliably transmitted on noisy and inaccurate wires
Course notes Preview Bits and Bytes Up next: Integer Values
Counting in base-2 (binary)
Base 2 Number Representation (not characters or strings) Represent 246710 as 1001101000112
value 211 210 29 28 27 26 25 24 23 22 21 20 value 2048 1024 512 256 128 64 32 16 8 4 2 1 Bits 1 0 0 1 1 0 1 0 0 0 1 1 add: 2048 + 256 +128 + 32 + 2+ 1 Sum: 2467
Represent 1.2010 as 1.0011001100110011[0011]…2
value 20 2−1 2−2 2−3 2−4 2−5 2−6 2−7 2−8 2−9 2−10 …
value 1 1 1 1 1 1 1 1 1 1 1 …
2 4 8 16 32 64 128 256 512 1024
Bits 1 0 0 1 1 0 0 1 1 0 0 1 1
Course notes Preview Bits and Bytes Up next: Integer Values
Encoding Byte Values
hex
decimal
binary
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
1 Byte = 8 bits
Binary 000000002 to 111111112
Decimal 010 to 25510 Hexadecimal 0016 to FF16
Hexadecimal: Base 16 representation Use characters 0 to 9 and A to F
WriteFA 1D 37 B1inCas: 0xFA1D37B1
0xfa1d37b1
Important to get comfortable with this notation Used in all subsequent labs
Practice problems 2.1, 2.2, 2.3, 2.4 will help you build your hex-literacy
Course notes Preview Bits and Bytes Up next: Integer Values
Example Data Representations
C Data Type char short
int
long float double long double pointer
Typical 32-bit 1
2
4
4
4
8
–
4
Typical 64-bit 1
2
4
8
4
8
–
8
x86-64 1
2
4
8
4
8 10/16 8
Size in Bytes
Course notes Preview Bits and Bytes Up next: Integer Values
Course notes 1 Preview
2 Bits and Bytes
Representing information as bits
Bit-level manipulations
Boolean Algebra
Logical operators Shift operators
3 Up next: Integer Values
Course notes Preview Bits and Bytes Up next: Integer Values
Boolean Algebra
Algebraic representation of logic, developed by Boole in 1850s Encodes “True” as 1 and “False” as 0
Binary AND:
A&B = 1 when
both A = 1 and B = 1
Binary OR:
A|B = 1 when
either A = 1 or B = 1
&01 |01 000 001 101 111
Binary NOT (complement): Exclusive-Or (XOR):
∼ A = 1 when A = 0 A ∧ B = 1 when either A = 1
or B = 1 but not both
∼1
01 ∧01 10 001
Based on Figure 2.7 in CS:APP3e
110
Course notes Preview Bits and Bytes Up next: Integer Values
Boolean Algebra extended
The connection between Boolean algebra and digital logic was first proposed by Claude Shannon in a 1937 Master’s thesis.
Can operate on bit vectors, applying operation bitwise
01101001 01101001 01101001
& 01010101 | 01010101 ˆ 01010101 ̃ 01010101
01000001 01111101 00111100 10101010
105 & 85 = 65 ??
(Bitwise operations look strange when using decimal representations!)
Course notes Preview Bits and Bytes Up next: Integer Values
Boolean Algebra and finite sets
Width w bit vector represents subsets of {0, … , w-1} aj =1ifj∈A
01101001 {0,3,5,6} 76543210
01010101 {0,2,4,6} 76543210
Operations (on the two sets given above):
& Intersection
| Union
ˆ Symmetric difference ̃ Complement
01000001 { 0 , 6 } 01111101 {0,2,3,4,5,6} 00111100 { 2, 3, 4, 5 } 10101010 { 1, 3, 5, 7 }
Course notes Preview Bits and Bytes Up next: Integer Values
Some useful properties of Boolean Algebra
Shared properties
Property
Commutativity
Integer ring
Boolean algebra
a|b=b|a a&b=b&a
Associativity
(a | b) | c = a | (b | c) (a & b) & c = a & (b & c)
Distributivity
Identities
a & (b | c) = (a & b) | (a & c)
a|0=a a&1=a
Annihilator
Cancellation
a&0=0
̃( ̃a) = a
Inverse
a+b=b+a
a×b=b×a
(a + b) + c = a + (b + c)
(a × b) × c = a × (b × c) a×(b+c) = (a×b)+(a×c) a+0=a
a×1=a
a×0=0
−(−a) = a
Unique to Rings
Unique to Boolean Algebras
a + −a = 0
— —
—
Distributivity
Complement
—
a | (b & c) = (a | b) & (a | c)
— —
a | ̃a = 1 a & ̃a = 0
Idempotency
a&a=a a|a=a
Absorption
— —
a | (a & b) = a a & (a | b) = a
DeMorgan’s laws
— —
̃(a & b) = ̃a | ̃b ̃(a | b) = ̃a & ̃b
Course notes Preview Bits and Bytes Up next: Integer Values Figure 2: Comparison of integer ring and Boolean algebra. The two mathematical structures share
Bit Masks
10010101 data & 00011100 mask = 00010100 result
Unwanted bits are
“masked out”: 00010100
Course notes Preview Bits and Bytes Up next: Integer Values
Logical operators
Don’t confuse bitwise and logical operators! They look similar but are very different. &&, || , !
– View 0 as “False”
– View anything non-zero as “True”
– Always return 0 or 1
– Early termination!
Examples:
!0x41 ⇒ 0x00
!0x00 ⇒ 0x01
!!0x41 ⇒ 0x01
0x69 && 0x55 ⇒ 0x01
0x69 || 0x55 ⇒ 0x01
a && 5/a (will never divide by zero) p && *p (avoids null pointer access)
Course notes Preview Bits and Bytes Up next: Integer Values
Shift operators
Left Shift: x << y
- Shift bitvector x left y positions
(Throw away extra bits on left)
- Fill with 0s on right
Right Shift: x >> y
– Shift bitvector x right y positions
(Throw away extra bits on right)
⋆ Logical shift: fill with 0s on left
⋆ Arithmetic shift: Replicate most significant bit on left
Undefined: Shift < 0 or ≥ word size
Example 1
Argument x << 3 Log. >> 2 Arith. >> 2
01100010
00010000
00011000
00011000
Example 2
Argument x << 3 Log. >> 2 Arith. >> 2
10100010
00010000
00101000
11101000
Course notes Preview Bits and Bytes Up next: Integer Values
Course notes 1 Preview
2 Bits and Bytes Boolean Algebra
Logical operators Shift operators
3 Up next: Integer Values Signed and Unsigned ints
Course notes Preview Bits and Bytes Up next: Integer Values
Encoding Integer values
Unsigned
w−1 B2U(X)=xi ·2i
i=0
Signed B2T(X)=−xw−1·2w−1+xi ·2i
Change: Sign bit!
w−2 B2T(X)=−xw−1 ·2w−1 +xi ·2i
Change: Sign bit! Example using short in C (2 bytes):
This is called Two’s complement
Sign bit indicates sign
– 0 for non-negative
– 1 for negative
w−2 i=0
i=0
Decimal
Hex
Binary
2467 -2467
09A3 F65D
00001001 10100011 11110110 01011101
Course notes Preview Bits and Bytes Up next: Integer Values
Unsigned Integers
23 = 8
22 = 4
21 = 2
20 = 1
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
[0001] [0101] [1011] [1111]
Course notes Preview Bits and Bytes Up next: Integer Values
Signed Integers
[1011] [1111]
– 23 = –8 23 = 8
22 = 4
21 = 2
20 = 1
–8–7–6–5–4–3–2–1 0 1 2 3 4 5 6 7 8 9 10 111213141516
+16
+16
Course notes Preview Bits and Bytes Up next: Integer Values
Back to the 2’s complement encoding example
short int x= 2467: 00001001 10100011 short int y= -2467: 11110110 01011101
Weight
1 2 4 8
16 32 64
128
2467
11 12 00 00 00 1 32 00 1 128
-2467
11 00 14 18 1 16 00 1 64 00
256
512 1024 2048 4096 8192 16384 -32768
1 256 00 00 1 2048 00 00 00 00
00 1 512 1 1024 00 1 4096 1 8192 1 16384 1 -32768
Sum:
2467
-2467
Course notes Preview Bits and Bytes Up next: Integer Values