Carnegie Mellon

14-513 18-613

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 1

 Carnegie Mellon

From Bits through Integers

15-213/15-513:
Introduction to Computer Systems Instructors:
Brian Railing (15-213 / 15-513)
2nd Lecture, May 15, 2024

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 2

 Carnegie Mellon

Bits, Bytes, and Integers

 Representing information as bits CSAPP 2.1
 Bit-level manipulations
 Integers CSAPP 2.2
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting CSAPP 2.3
 Byte Ordering CSAPP 2.1.3

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 3

 Carnegie Mellon

Analog Computers
 Before digital computers there were analog computers.

 Consider a couple of simple analog computers:

▪ A simple circuit can allow one to adjust voltages using variable
resistors and measure the output using a volt meter:
▪ A simple network of adjustable parallel resistors can allow one to
find the average of the inputs.

https://www.daycounter.com/Calculators/Voltage-Summer/Voltage-
Summer-Calculator.phtml
https://www.quora.com/What-is-the-most-basic-voltage-adder-circuit-
without-a-transistor-op-amp-and-any-external-supply

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 4

 Carnegie Mellon

Needing Less Accuracy, Precision is Better

 We don’t try to measure exactly
▪ We just ask, is it high enough to be “On”, or
▪ Is it low enough to be “Off”.

 We have two states, so we have a binary, or 2-ary, system.

▪ We represent these states as 0 and 1

 Now we can easily interpret, communicate, and duplicate signals well enough to know
what they mean.
0 1 0

1.1V
0.9V

0.2V
0.0V
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 5
 Carnegie Mellon

Binary Representation
 Binary representation leads to a simple binary, i.e. base-2,
numbering system
▪ 0 represents 0
▪ 1 represents 1
▪ Each “place” represents a power of two, exactly as each place in our
usual “base 10”, 10-ary numbering system represents a power of 10
 By encoding/interpreting sets of bits in various ways, we
can represent different things:
▪ Operations to be executed by the processor, numbers, enumerable
things, such as text characters
 As long as we can assign it to a discrete number, we can
represent it in binary

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 6

 Carnegie Mellon

Binary Representation:
Simple Numbers
 For example, we can count in binary, a base-2 numbering
system
▪ 000, 001, 010, 011, 100, 101, 110, 111, …
▪ 000 = 0*22 + 0*21 + 0*20 = 0 (in decimal)
▪ 001 = 0*22 + 0*21 + 1*20 = 1 (in decimal)
▪ 010 = 0*22 + 1*21 + 0*20 = 2 (in decimal)
▪ 011 = 0*22 + 1*21 + 1*20 = 3 (in decimal)
▪ Etc.
 For reference, consider some base-10 examples:
▪ 000 = 0*102 + 0*101 + 0*100
▪ 001 = 0*102 + 0*101 + 1*100
▪ 357 = 3*102 + 5*101 + 7*100

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 7

 Carnegie Mellon

Hexadecimal and Octal

 Writing out numbers in binary takes too many digits

 We want a way to represent numbers more densely such that

fewer digits are required
▪ But also such that it is easy to get at the bits that we want

 Any power-of-two base provides this property

▪ Octal, e.g. base-8, and hexadecimal, e.g. base-16 are the closest to our
familiar base-10.
▪ Each has been used by “computer people” over time
▪ Hexadecimal is often preferred because it is denser.

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 8

 Carnegie Mellon

Hexadecimal
 Hexadecimal 0016 to FF16
0 0 0000
▪ Base 16 number representation 1 1 0001
▪ Use characters ‘0’ to ‘9’ and ‘A’ to ‘F’ 2 2 0010
3 3 0011
4 4 0100
5 5 0101
 Consider 1A2B in Hexadecimal: 6 6 0110
▪ 1*163 + A*162 + 2*161 + B*160 7 7 0111
8 8 1000
▪ 1*163 + 10*162 + 2*161 + 11*160 = 6699 (decimal) 9 9 1001
A 10 1010
B 11 1011
C 12 1100
▪ The C Language prefixes hexadecimal numbers with “0x” D 13 1101
so they aren’t confused with decimal numbers E 14 1110
F 15 1111
▪ Write FA1D37B16 in C as
▪ 0xFA1D37B
▪ 0xfa1d37b 15213: 0011 1011 0110 1101
3 B 6 D
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
 Byte Ordering

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 10

 Carnegie Mellon

Boolean Algebra
 Developed by George Boole in 19th Century
▪ Algebraic representation of logic
▪ Encode “True” as 1 and “False” as 0

And Or
◼ A&B = 1 when both A=1 and B=1 ◼ A|B = 1 when either A=1 or B=1

Not Exclusive-Or (Xor)

◼ ~A = 1 when A=0 ◼ 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 11

 Carnegie Mellon

General Boolean Algebras

 Operate on Bit Vectors
▪ Operations applied bitwise
01101001 01101001 01101001
& 01010101 | 01010101 ^ 01010101 ~ 01010101
01000001
01000001 01111101
01111101 00111100
00111100 10101010
10101010

 All of the Properties of Boolean Algebra Apply

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 12

 Carnegie Mellon

Example: Representing & Manipulating Sets

 Representation
▪ Width w bit vector represents subsets of {0, …, w–1}
▪ aj = 1 if j ∈ A

▪ 01101001 { 0, 3, 5, 6 }
▪ 76543210

▪ 01010101 { 0, 2, 4, 6 }
▪ 76543210
 Operations
▪ & Intersection 01000001 { 0, 6 }
▪ | Union 01111101 { 0, 2, 3, 4, 5, 6 }
▪ ^ Symmetric difference 00111100 { 2, 3, 4, 5 }
▪ ~ Complement 10101010 { 1, 3, 5, 7 }
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 13
 Carnegie Mellon

Bit-Level Operations in C
 Operations &, |, ~, ^ Available in C 0 0 0000
▪ Apply to any “integral” data type 1 1 0001
2 2 0010
▪ long, int, short, char, unsigned 3 3 0011
▪ View arguments as bit vectors 4 4 0100
5 5 0101
▪ Arguments applied bit-wise 6 6 0110
7 7 0111
 Examples (Char data type) 8 8 1000
▪ ~0x41 → 0xBE 9 9 1001
A 10 1010
~010000012 → 101111102
▪ B 11 1011
▪ ~0x00 → 0xFF C 12 1100
D 13 1101
▪ ~000000002 → 111111112 E 14 1110
▪ 0x69 & 0x55 → 0x41 F 15 1111
▪ 011010012 & 010101012 → 010000012
▪ 0x69 | 0x55 → 0x7D
▪ 011010012 | 010101012 → 011111012

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 14

 Carnegie Mellon

Bit-Level Operations in C
 Operations &, |, ~, ^ Available in C 0 0 0000
▪ Apply to any “integral” data type 1 1 0001
2 2 0010
▪ long, int, short, char, unsigned 3 3 0011
▪ View arguments as bit vectors 4 4 0100
5 5 0101
▪ Arguments applied bit-wise 6 6 0110
7 7 0111
 Examples (Char data type) 8 8 1000
▪ ~0x41 → 0xBE 9 9 1001
A 10 1010
~010000012 → 101111102
▪ B 11 1011
▪ ~0x00 → 0xFF C 12 1100
D 13 1101
▪ ~000000002 → 111111112 E 14 1110
▪ 0x69 & 0x55 → 0x41 F 15 1111
▪ 011010012 & 010101012 → 010000012
▪ 0x69 | 0x55 → 0x7D
▪ 011010012 | 010101012 → 011111012

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 15

 Carnegie Mellon

Bit-Level Operations in C
 Operations &, |, ~, ^ Available in C
0 0 0000
▪ Apply to any “integral” data type 1 1 0001
▪ long, int, short, char, unsigned 2 2 0010
3 3 0011
▪ View arguments as bit vectors 4 4 0100
5 5 0101
▪ Arguments applied bit-wise 6 6 0110
 Examples (Char data type) 7 7 0111
8 8 1000
▪ ~0x41 → 1011 11100xBE~010000012 → 101111102 9 9 1001
▪ ~0x00 → 1111 11110xF~000000002 → 1111112 A 10 1010
B 11 1011
▪ 0x69 & 0x55: 0x69 | 0x55: C 12 1100
0110 1001 0110 1001 D 13 1101
E 14 1110
& 0101 0101 | 0101 0101 F 15 1111
----------------- -----------------
0100 0001011010 0111 1101011010012 012 & 010101012 → 010000012
0x7D
▪ 011010012 | 010101012 → 011111012
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 16
 Carnegie Mellon

Contrast: Logic Operations in C

 Contrast to Bit-Level Operators
▪ Logic Operations: &&, ||, !
▪ View 0 as “False”
▪ Anything nonzero as “True”
▪ Always return 0 or 1
▪ Early termination
 Examples (char data type) Watch out for && vs. & (and || vs. |)…
▪ !0x41 → 0x00 Super common C programming pitfall!
▪ !0x00 → 0x01
▪ !!0x41→ 0x01

▪ 0x69 && 0x55 → 0x01

▪ 0x69 || 0x55 → 0x01
▪ p && *p (avoids null pointer access)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 17

 Carnegie Mellon

Shift Operations
 Left Shift: x << y Argument x 01100010
▪ Shift bit-vector x left y positions << 3 00010000
– Throw away extra bits on left Log. >> 2 00011000
▪ Fill with 0’s on right
Arith. >> 2 00011000
 Right Shift: x >> y
▪ Shift bit-vector x right y positions
Argument x 10100010
Throw away extra bits on right
▪
▪ Logical shift << 3 00010000
▪ Fill with 0’s on left Log. >> 2 00101000
▪ Arithmetic shift Arith. >> 2 11101000
▪ Replicate most significant bit on left

 Undefined Behavior
▪ Shift amount < 0 or ≥ word size
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 18
 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

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 19

 Carnegie Mellon

Binary Number Lines

 In binary, the number of bits in the data type size
determines the number of points on the number line.
▪ We can assign the points any meaning we’d like

 Consider the following examples:

▪ 1 bit number line

0 1
▪ 2 bit number line

00 01 10 11
▪ 3 bit number line

000 001 010 011 100 101 110 111

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 20
 Carnegie Mellon

Some Purely Imaginary Examples

 3 bit number line

-1/16 -1/8 -1/4 0 1/16 1/8 1/4 1/2

0 1 2 3 4 5 6 7

-4 -3 -2 -1 0 1 2 3

A B C D E F G H

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 21

 Carnegie Mellon

Overflow
 Let’s consider a simple 3 digit number line:

0 1 2 3 4 5 6 7
000 001 010 011 100 101 110 111

 What happens if we add 1 to 7?

▪ In other words, what happens if we add 1 to 111?

 111+ 001 = 1 000

▪ But, we only get 3 bits – so we lose the leading-1.
▪ This is called overflow

 The result is 000

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 22
 Carnegie Mellon

Modulus Arithmetic
 Let’s explore this idea of overflow some more
▪ 111 + 001 = 1 000 = 000
▪ 111 + 010 = 1 001 = 001
▪ 111 + 011 = 1 010 = 010
▪ 111 + 100 = 1 011 = 011
▪ …
▪ 111 + 110 = 1 101 = 101
▪ 111 + 111 = 1 110 = 110

 So, arithmetic “wraps around” when it gets “too positive”

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 23

 Carnegie Mellon

Unsigned and Non-Negative Integers

 We’ll use the term “ints” to mean the finite set of integer
numbers that we can represent on a number line enumerated
by some fixed number of bits, i.e. bit width.

 We normally represent unsigned and non-negative int using

simple binary as we have already discussed
▪ An “unsigned” int is any int on a number line, e.g. of a data type, that
doesn’t contain any negative numbers
▪ A non-negative number is a number greater than or equal to (>=) 0 on a
number line, e.g. of a data type, that does contain negative numbers

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 24

 Carnegie Mellon

How represent negative Numbers?

 We could use the leading bit as a sign bit:
▪ 0 means non-negative
▪ 1 means negative

000 001 010 011 100 101 110 111

0 1 2 3 -0 -1 -2 -3

 This has some benefits

▪ It lets us represent negative and non-negative numbers
▪ 0 represents 0

 It also has some drawbacks

▪ There is a -0, which is the same as 0, except that it is different
▪ How to add such numbers 1 + -1 should equal 0
▪ But, by simple math, 001 + 101 = 110, which is -2?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 25
 Carnegie Mellon

A Magic Trick!
 Let’s just start with three ideas:
▪ 1 should be represented as 1
▪ -1 + 1 = 0
▪ We want addition to work in the familiar way, with simple rules.

 We want a situation where “-1” + 1 = 0

 Consider a 3 bit number:

▪ 001 + “-1” = 0
▪ 001 + 111 = 0
▪ Remember 001 + 111 = 1 000, and the leading one is lost to
overflow.
 “-1” = 111
▪ Yep!
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 26
 Carnegie Mellon

Negative Numbers
 Well, if 111 is -1, what is -2?
▪ -1 - 1
▪ 111 – 001 = 110

 Does that really work?

▪ If it does -2 + 2 = 0
▪ 110 + 010 = 1 000 = 000

 -2 + 5 should be 3, right?
▪ 110 + 101 = 1 011 = 011

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 27

 Carnegie Mellon

Finding –x the easy way

 Given a non-negative number in binary, e.g. 5, represented
with a fixed bit width, e.g. 4
▪ 0101

 We can find its negative by flipping each bit and adding 1

▪ 0101 This is 5
▪ 1010 This is the “ones complement of 5”, e.g. 5 with bits flipped
▪ 1011 This is the “twos complement of 5”, e.g. 5 with the bits
flipped and 1 added
▪ 0101 + 1011 = 1 0000 = 0000
▪ -x = ~x+1

 Because of the fixed width, the “two’s complement” of a

number can be used as its negative.
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 28
 Carnegie Mellon

Why Does This Work?

 Consider any number and its (ones) complement:
▪ 0101
▪ 1010

 They are called complements because complementary bits

are set. As a result, if they are added, all bits are necessarily
set:
▪ 0101 + 1010 = 1111

 Adding 1 to the sum of a number and its complement

necessarily results in a 0 due to overflow
▪ (0101 + 1010) + 1 = 1111 + 1 = 1 0000 = 0000

 And if x + y = 0, y must equal –x

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 29
 Carnegie Mellon

Why Does This Work? Cont.

 If x + y = 0
▪ y must equal –x

 So if x + (Complement(x) + 1) = 0
▪ Complement(x) + 1 must equal –x

 Another way of looking at it:

▪ if x + (Complement(x) + 1) = 0
▪ x + Complement(x) = -1
▪ x = -1 - Complement(x)
▪ -x = 1 + Complement(x)

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 30

 Carnegie Mellon

Visualizing Two’s Complement

 Numbers “wrap around” with -1 at the very end

000 001 010 011 100 101 110 111

0 1 2 3 -4 -3 -2 -1

 A few things to note:

▪ All negative numbers start with a ”1”
E.g. 100 is “-4”
▪
▪ You can view the leading “1” as introducing a “-4”
▪ E.g. 101 = 1*-4+0*2+1*1= -3
▪ But 010 = 0*-4+1*2+0*1 = 2
▪ -4 is missing a positive partner

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 31

 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 (The most negative two’s complement number)

Decimal Hex Binary
x -32768 80 00 10000000 00000000
~x 32767 7F FF 01111111 11111111
~x+1 -32768 80 00 10000000 00000000

Canonical counter example

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 32

 Carnegie Mellon

Encoding Integers: Dense Form

Unsigned Two’s Complement
w−1 w−2
 xi 2  xi 2
i w−1 i
B2U(X ) = B2T (X ) = − xw−1 2 +
i=0 i=0

short int x = 15213;

short int y = -15213;
Sign
 C does not mandate using two’s complement
▪ But, most machines do, and we will assume so Bit
 C short (2 bytes long)
Decimal Hex Binary
x 15213 3B 6D 00111011 01101101
y -15213 C4 93 11000100 10010011

 Sign Bit
▪ For 2’s complement, most significant bit indicates sign
▪ 0 for nonnegative, 1 for negative
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 33
 Carnegie Mellon

Numeric Ranges
 Unsigned Values
 Two’s Complement Values
▪ UMin = 0
▪ TMin = –2w–1
000…0
100…0
▪ UMax = 2w –1
▪ TMax = 2w–1 – 1
111…1
011…1
▪ Minus 1
111…1

Values for W = 16
Decimal Hex Binary
UMax 65535 FF FF 11111111 11111111
TMax 32767 7F FF 01111111 11111111
TMin -32768 80 00 10000000 00000000
-1 -1 FF FF 11111111 11111111
0 0 00 00 00000000 00000000

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 34

 Carnegie Mellon

Quiz Time!

Check out:

https://canvas.cmu.edu/courses/40739/quizzes/123408

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
 Byte Ordering

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 36

 Carnegie Mellon

Mapping Signed  Unsigned

Bits Signed Unsigned
0000 0 0
0001 1 1
0010 2 2
0011 3 = 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 -8 8
1001 -7 9
1010 -6 10
+/- 16
1011 -5 11
1100 -4 12
1101 -3 13
1110 -2 14
1111 -1 15
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 37
 Carnegie Mellon

Relation between Signed & Unsigned

Two’s Complement Unsigned

T2U
x T2B B2U ux
X

Maintain Same Bit Pattern

w–1 0
ux + + + ••• + + +
x - + + ••• + + +

Large negative weight

becomes
Large positive weight

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 38

 Carnegie Mellon

Conversion Visualized
 2’s Comp. → Unsigned
▪ Ordering Inversion UMax
▪ Negative → Big Positive UMax – 1

TMax + 1 Unsigned
TMax TMax Range

2’s Complement 0 0
Range –1
–2

TMin
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 39
 Carnegie Mellon

Signed vs. Unsigned in C

 Constants
▪ By default are considered to be signed integers
▪ Unsigned if have “U” as suffix
0U, 4294967259U
 Casting
▪ 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

tx = ux; int fun(unsigned u);
uy = ty; uy = fun(tx);

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 40

 Carnegie Mellon

Casting Surprises
 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 = -2,147,483,648 , TMAX = 2,147,483,647
 Constant1 Constant2 Relation Evaluation
0 0 0U 0U == unsigned
-1 -1 0 0 < signed
-1 -1 0U 0U > unsigned
2147483647
2147483647 -2147483647-1
-2147483648 > signed
2147483647U
2147483647U -2147483647-1
-2147483648 < unsigned
-1 -1 -2 -2 > signed
(unsigned)-1
(unsigned) -1 -2 -2 > unsigned
2147483647
2147483647 2147483648U
2147483648U < unsigned
2147483647
2147483647 (int) (int)
2147483648U
2147483648U > signed
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 41
 Carnegie Mellon

Summary
Casting Signed Unsigned: Basic Rules
 Bit pattern is maintained
 But reinterpreted

 Can have unexpected effects: adding or subtracting 2w

 Expression containing signed and unsigned int

▪ int is cast to unsigned!!

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 42

 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
 Byte Ordering

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 43

 Carnegie Mellon

Sign Extension
 Task:
▪ Given w-bit signed integer x
▪ Convert it to w+k-bit integer with same value
 Rule:
▪ Make k copies of sign bit:
▪ X’ = xw–1 ,…, xw–1 , xw–1 , xw–2 ,…, x0

k copies of MSB w

X •••

•••

X’
••• •••
k w
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 44
 Carnegie Mellon

Sign Extension: Simple Example

Positive number Negative number

-16 8 4 2 1 -16 8 4 2 1

10 = 0 1 0 1 0 -10 = 1 0 1 1 0

-32 16 8 4 2 1 -32 16 8 4 2 1

10 = 0 0 1 0 1 0 -10 = 1 1 0 1 1 0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 45

 Carnegie Mellon

Truncation
 Task:
▪ Given k+w-bit signed or unsigned integer X
▪ Convert it to w-bit integer X’ with same value for “small enough” X
 Rule:
▪ Drop top k bits:
▪ X’ = xw–1 , xw–2 ,…, x0

k w
X ••• •••

•••
X’ •••
w
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 46
 Carnegie Mellon

Truncation: Simple Example

No sign change Sign change
-16 8 4 2 1 -16 8 4 2 1

2 = 0 0 0 1 0 10 = 0 1 0 1 0

-8 4 2 1 -8 4 2 1

2 = 0 0 1 0 -6 = 1 0 1 0
2 mod 16 = 2 10 mod 16 = 10U mod 16 = 10U = -6

-16 8 4 2 1 -16 8 4 2 1

-6 = 1 1 0 1 0 -10 = 1 0 1 1 0

-8 4 2 1 -8 4 2 1

-6 = 1 0 1 0 6 = 0 1 1 0
-6 mod 16 = 26U mod 16 = 10U = -6 -10 mod 16 = 22U mod 16 = 6U = 6

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 47

 Carnegie Mellon

Summary:
Expanding, Truncating: Basic Rules
 Expanding (e.g., short int to int)
▪ Unsigned: zeros added
▪ Signed: sign extension
▪ Both yield expected result

 Truncating (e.g., unsigned to unsigned short)

▪ Unsigned/signed: bits are truncated
▪ Result reinterpreted
▪ Unsigned: mod operation
▪ Signed: similar to mod
▪ For small (in magnitude) numbers yields expected behavior

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 48

 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
 Byte Ordering

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 49

 Carnegie Mellon

Unsigned Addition
Operands: w bits u •••
+v •••
True Sum: w+1 bits
u+v •••
Discard Carry: w bits UAddw(u , v) •••

 Standard Addition Function 0 0 0000

1 1 0001
▪ Ignores carry output 2 2 0010
3 3 0011
 Implements Modular Arithmetic 4 4 0100
5 5 0101
s = UAddw(u , v) = u + v mod 2w 6 6 0110
7 7 0111
unsigned char 8 8 1000
1110 1001 E9 223 9 9 1001
+ 1101 0101 + D5 + 213 A 10 1010
B 11 1011
1 1011 1110 1BE 446 C 12 1100
D 13 1101
1011 1110 BE 190 E 14 1110
F 15 1111
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 50
 Carnegie Mellon

Two’s Complement Addition

Operands: w bits u •••
+ v •••
True Sum: w+1 bits
u+v •••
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
▪ Will give s == t 1110 1001 E9 -23
+ 1101 0101 + D5 + -43
1 1011 1110 1BE -66
1011 1110 BE -66
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 51
 Carnegie Mellon

Visualizing “True Sum” Integer Addition

 Integer Addition Add4(u , v)
▪ 4-bit integers u, v Integer Addition

▪ Compute true sum

Add4(u , v)
▪ Values increase linearly 32
with u and v 28

▪ Forms planar surface 24

20
16
14
12 12
8 10
8
4
0 4
6
v
0
2 2
4
6
u 8
10
12
14
0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 52

 Carnegie Mellon

Visualizing Unsigned Addition

 Wraps Around Overflow

▪ If true sum ≥ 2w
▪ At most once UAdd4(u , v)

True Sum 16
14
2w+1 Overflow 12
10
8
2w 6 12
14

4 10
8
2
6 v
0 0 4

Modular Sum 0
2
4
6
2

u 8
10
12
14
0

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 53

 Carnegie Mellon

Visualizing 2’s Complement Addition

NegOver

 Values
▪ 4-bit two’s comp. TAdd4(u , v)
▪ Range from -8 to +7
 Wraps Around
8
▪ If sum  2w–1 6

Becomes negative
▪
4
2

▪ At most once 0
6
-2 4
▪ If sum < –2w–1 -4 2
0
-6
▪ Becomes positive -8
-2

▪ At most once
-8
-6
-4 -6
-4
v
-2
0 -8
2
u 4
6 PosOver

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 54

 Carnegie Mellon

Multiplication
 Goal: Computing Product of w-bit numbers x, y
▪ Either signed or unsigned
 Result: Same as computing ideal, exact result x*y and keeping
w lower bits.
 Ideal,exact results can be bigger than w bits
▪ Worst case is up to 2w bits
▪ Unsigned, because all bits are magnitude
▪ Signed, but only for Tmin*Tmin, because anything added to Tmin
reduces its magnitude and Tmax is less than Tmin.
 So, maintaining exact results…
▪ would need to keep expanding word size with each product computed
▪ Impossible in hardware (at least without limits), as all resources are finite
▪ In practice, 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 55
 Carnegie Mellon

Power-of-2 Multiply with Shift

 Operation
▪ u << k gives u * 2k
▪ Both signed and unsigned k
u •••
Operands: w bits
* 2k 0 ••• 0 1 0 ••• 0 0

True Product: w+k bits u · 2k ••• 0 ••• 0 0

Discard k bits: w bits UMultw(u , 2k) ••• 0 ••• 0 0

TMultw(u , 2k)
 Examples
▪ u << 3 == u * 8
▪ (u << 5) – (u << 3) == u * 24
▪ Most machines shift and add faster than multiply
▪ Compiler generates this code automatically

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 56

 Carnegie Mellon

Unsigned Power-of-2 Divide with Shift

 Quotient of Unsigned by Power of 2
▪ u >> k gives  u / 2k 
▪ Uses logical shift
k
u ••• ••• Binary Point
Operands:
/ 2k 0 ••• 0 1 0 ••• 0 0

Division: u / 2k 0 ••• 0 0 ••• . •••

Result:  u / 2k  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 57

 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 to the left, not towards zero (Unlikely to be what is expected, introduces a
bias).
k
x ••• ••• Binary Point
Operands:
/ 2k 0 ••• 0 1 0 ••• 0 0

Division: x / 2k 0 ••• ••• . •••

Result: RoundDown(x / 2k) 0 ••• •••
Division Computed Hex Binary
x -15213 -15213 C4 93 11000100 10010011
x >> 1 -7606.5 -7607 E2 49 11100010 01001001
x >> 4 -950.8125 -951 FC 49 11111100 01001001
x >> 8 -59.4257813 -60 FF C4 11111111 11000100

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 58

 Carnegie Mellon

Round-toward-0 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<<k)-1) >> k
▪ Biases dividend toward 0

Case 1: No rounding k
Dividend: u 1 ••• 0 ••• 0 0
+2k –1 0 ••• 0 0 1 ••• 1 1
1 ••• 1 ••• 1 1 Binary Point
Divisor: / 2k 0 ••• 0 1 0 ••• 0 0

 u / 2k  0 •••
1 1 1 1 ••• . 1 ••• 1 1

Biasing has no effect

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 59
 Carnegie Mellon

Correct Power-of-2 Divide (Cont.)

Case 2: Rounding
k
Dividend: x 1 ••• •••
+2k –1 0 ••• 0 0 1 ••• 1 1
1 ••• •••

Incremented by 1 Binary Point

Divisor: / 2k 0 ••• 0 1 0 ••• 0 0
 x / 2k  0 •••
1 1 1 1 ••• . •••

Incremented by 1
Biasing adds 1 to final result
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 60
 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
 Byte Ordering

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 61

 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

 Becomes a concern when data is communicated

▪ Over a network, via files, etc.
 Important notes
▪ Bits are not reversed, as the low order bit is the reference point.
▪ Doesn’t affect chars, or strings (arrays of chars), as chars are only one byte

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 62

 Carnegie Mellon

Byte Ordering Example

 Example
▪ Variable x has 4-byte value of 0x01234567
▪ Address given by &x is 0x100

Big Endian 0x100 0x101 0x102 0x103

01 23 45 67

Little Endian 0x100 0x101 0x102 0x103

67 45 23 01

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 63

 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 Assembly Rendition
8048365 5b pop %ebx
8048366 81 c3 ab 12 00 00 add $0x12ab,%ebx
804836c 83 bb 28 00 00 00 00 cmpl $0x0,0x28(%ebx)

 Deciphering Numbers
▪ Value: 0x12ab
▪ Pad to 32 bits: 0x000012ab
▪ Split into bytes: 00 00 12 ab
▪ Reverse: ab 12 00 00

Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 64

 Carnegie Mellon

Today: Bits, Bytes, and Integers

 Representing information as bits CSAPP 2.1
 Bit-level manipulations
 Integers CSAPP 2.2
▪ Representation: unsigned and signed
▪ Conversion, casting
▪ Expanding, truncating
▪ Addition, negation, multiplication, shifting CSAPP 2.3
 Byte Ordering CSAPP 2.1.3

Questions?
Bryant and O’Hallaron, Computer Systems: A Programmer’s Perspective, Third Edition 65