The Hardware/Software Interface CSE351 Spring 2011 April 4, 2011: Integers (and more about C pointers)
Integers I
http://xkcd.com/257/
CS295
L04: Integers I
1
Roadmap
2
car *c = malloc(sizeof(car));
c->miles = 100;
c->gals = 17;
float mpg = get_mpg(c);
free(c);
Car c = new Car();
c.setMiles(100);
c.setGals(17);
float mpg =
c.getMPG();
Java:
C:
Assembly language:
Machine code:
0111010000011000
100011010000010000000010
1000100111000010
110000011111101000011111
Computer system:
OS:
Memory & data
Arrays & structs
Integers & floats
RISC V assembly
Procedures & stacks
Executables
Memory & caches
Processor Pipeline
Performance
Parallelism
CS295
L04: Integers I
2
But before we get to integers….
Encode a standard deck of playing cards
52 cards in 4 suits
How do we encode suits, face cards?
What operations do we want to make easy to implement?
Which is the higher value card?
Are they the same suit?
3
CS295
L04: Integers I
Value comparison: War
Same suit: Crazy Eights
Boolean Algebra
Developed by George Boole in 19th Century
Algebraic representation of logic (True 1, False 0)
AND: A&B=1 when both A is 1 and B is 1
OR: A|B=1 when either A is 1 or B is 1
XOR: A^B=1 when either A is 1 or B is 1, but not both
NOT: ~A=1 when A is 0 and vice-versa
DeMorgan’s Law: ~(A|B) = ~A & ~B
~(A&B) = ~A | ~B
4
& 0 1
0 0 0
1 0 1
| 0 1
0 0 1
1 1 1
^ 0 1
0 0 1
1 1 0
~
0 1
1 0
AND
OR
XOR
NOT
CS295
L04: Integers I
General Boolean Algebras
Operate on bit vectors
Operations applied bitwise
All of the properties of Boolean algebra apply
Examples of useful operations:
,
5
01101001
& 01010101
01101001
| 01010101
01101001
^ 01010101
~ 01010101
01010101
| 11110000
11110101
01010101
^ 01010101
00000000
CS295
L04: Integers I
Now, how do we use the boolean operators?
Typically on ”bit vectors” (treat a byte, or multiple bytes) as a bit vector
Bit-Level Operations in C
& (AND), | (OR), ^ (XOR), ~ (NOT)
View arguments as bit vectors, apply operations bitwise
Apply to any “integral” data type
long, int, short, char, unsigned
Examples with char a, b, c;
a = (char) 0x41; // 0x41->0b 0100 0001
b = ~a; // 0b ->0x
a = (char) 0x69; // 0x69->0b 0110 1001
b = (char) 0x55; // 0x55->0b 0101 0101
c = a & b; // 0b ->0x
a = (char) 0x41; // 0x41->0b 0100 0001
b = a; // 0b 0100 0001
c = a ^ b; // 0b ->0x
6
CS295
L04: Integers I
Some bit-twiddling puzzles in Lab 1
Contrast: Logic Operations
Logical operators in C: && (AND), || (OR), ! (NOT)
0 is False, anything nonzero is True
Always return 0 or 1
Early termination (a.k.a. short-circuit evaluation) of &&, ||
int x = (42 == 6) || boom();
int y = (42 == 6) && boom();
Examples (char data type)
!0x41 -> 0x00
!0x00 -> 0x01
!!0x41 -> 0x01
7
0xCC && 0x33 -> 0x01
0x00 || 0x33 -> 0x01
CS295
L04: Integers I
Two possible representations
1 bit per card (52): bit corresponding to card set to 1
“One-hot” encoding (similar to set notation)
Drawbacks:
Hard to compare values and suits
Large number of bits required
1 bit per suit (4), 1 bit per number (13): 2 bits set
Pair of one-hot encoded values
Easier to compare suits and values, but still lots of bits used
8
low-order 52 bits of 64-bit word
4 suits
13 numbers
CS295
L04: Integers I
52 bits takes 7 bytes
17 bites takes 3 bytes
Two better representations
Binary encoding of all 52 cards – only 6 bits needed
Fits in one byte (smaller than one-hot encodings)
How can we make value and suit comparisons easier?
Separate binary encodings of suit (2 bits) and value (4 bits)
Also fits in one byte, and easy to do comparisons
9
low-order 6 bits of a byte
suit
value
♣ 00
♦ 01
♥ 10
♠ 11
K Q J . . . 3 2 A
1101 1100 1011 … 0011 0010 0001
CS295
L04: Integers I
Notice the arbitrariness of binary encoding choices: A is 1 instead of 0, ordering of suits
Compare Card Suits
char hand[5]; // represents a 5-card hand
char card1, card2; // two cards to compare
card1 = hand[0];
card2 = hand[1];
…
if ( isSameSuit(card1, card2) ) { … }
10
SUIT_MASK = 0x30 =
0
0
1
1
0
0
0
0
suit
value
mask: a bit vector designed to achieve a desired behavior when used with a bitwise operator on another bit vector v.
Here we turns all but the bits of interest in v to 0.
#define SUIT_MASK 0x30
int isSameSuit(char card1, char card2) {
return (card1 & SUIT_MASK) == (card2 & SUIT_MASK);
}
returns int
CS295
L04: Integers I
#define does text substitution
x & 0 = 0
x & 1 = x
Compare Card Suits
11
mask: a bit vector designed to achieve a desired behavior when used with a bitwise operator on another bit vector v.
Here we turns all but the bits of interest in v to 0.
#define SUIT_MASK 0x30
int isSameSuit(char card1, char card2) {
return (!((card1 & SUIT_MASK) ^ (card2 & SUIT_MASK)));
// return (card1 & SUIT_MASK) == (card2 & SUIT_MASK);
}
0 0 0 1 0 0 1 0
0 0 0 1 1 1 0 1
0 0 1 1 0 0 0 0
SUIT_MASK
0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
!(x^y) equivalent to x==y
🃂
🃎
&
=
^
!
=
&
CS295
L04: Integers I
What if you don’t wanna use “==”
Compare Card Values
12
VALUE_MASK = 0x0F =
0
0
0
0
1
1
1
1
suit
value
#define VALUE_MASK 0x0F
int greaterValue(char card1, char card2) {
return ((unsigned char)(card1 & VALUE_MASK) >
(unsigned char)(card2 & VALUE_MASK));
}
char hand[5]; // represents a 5-card hand
char card1, card2; // two cards to compare
card1 = hand[0];
card2 = hand[1];
…
if ( greaterValue(card1, card2) ) { … }
mask: a bit vector designed to achieve a desired behavior when used with a bitwise operator on another bit vector v.
CS295
L04: Integers I
0x0F = 0000_1111
Cast to unsigned because of two’s complement, later
Compare Card Values
13
#define VALUE_MASK 0x0F
int greaterValue(char card1, char card2) {
return ((unsigned int)(card1 & VALUE_MASK) >
(unsigned int)(card2 & VALUE_MASK));
}
0 0 1 0 0 0 1 0
🃂
0 0 1 0 1 1 0 1
🃎
0 0 0 0 1 1 1 1
VALUE_MASK
0 0 0 0 1 1 1 1
&
&
0 0 0 0 0 0 1 0
0 0 0 0 1 1 0 1
=
=
210 > 1310
0 (false)
mask: a bit vector designed to achieve a desired behavior when used with a bitwise operator on another bit vector v.
CS295
L04: Integers I
Integers
Binary representation of integers
Unsigned and signed
Casting in C
Consequences of finite width representation
Overflow, sign extension
Shifting and arithmetic operations
14
CS295
L04: Integers I
14
Encoding Integers
The hardware (and C) supports two flavors of integers
unsigned – only the non-negatives
signed – both negatives and non-negatives
Cannot represent all integers with bits
Only distinct bit patterns
Unsigned values: 0 … –1
Signed values: … 0 … –1
Example: 8-bit integers (e.g. char)
15
–
+
CS295
L04: Integers I
Okay, so now let’s talk some more about how we represent numbers, or integers to be specific
Multiple sizes of integers, using different numbers of bytes
But for each size, there are two ways of interpreting the bits…
Same width, just shifted
Unsigned Integers
Unsigned values follow the standard base 2 system
Add and subtract using the normal “carry” and “borrow” rules, just in binary
Useful formula: ones in a row =
How would you make signed integers?
16
00111111
+00001000
01000111
63
+ 8
71
CS295
L04: Integers I
“1’s place”, the “2’s place”, “4’s place”…
An important use of unsigned values in C is pointers – there are no negative memory addresses
What if we want to represent negative numbers?
Sign and Magnitude
Designate the high-order bit (MSB) as the “sign bit”
sign=0: positive numbers; sign=1: negative numbers
Benefits:
Using MSB as sign bit matches positive numbers with unsigned
All zeros encoding is still = 0
Examples (8 bits):
0x00 = 000000002 is non-negative, because the sign bit is 0
0x7F = 011111112 is non-negative (+12710)
0x85 = 100001012 is negative (-510)
0x80 = 100000002 is negative…
17
… zero???
Most Significant Bit
CS295
L04: Integers I
One possibility; some good things
0b0010 = 2 in signed or unsigned
Sign and Magnitude
MSB is the sign bit, rest of the bits are magnitude
Drawbacks?
18
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Unsigned
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 0
– 1
– 2
– 3
– 4
– 5
– 6
– 7
Sign and Magnitude
CS295
L04: Integers I
To help visualize these numbers, we’ll use this number wheel
Binary goes up clockwise
See how we start with +0 – +7 on right side
Then the left side, which starts with 1, are all negative, starting with -0 .. -7
Sign and Magnitude
MSB is the sign bit, rest of the bits are magnitude
Drawbacks:
Two representations of 0 (bad for checking equality)
19
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 0
– 1
– 2
– 3
– 4
– 5
– 6
– 7
Sign and Magnitude
CS295
L04: Integers I
Sign and Magnitude
MSB is the sign bit, rest of the bits are magnitude
Drawbacks:
Two representations of 0 (bad for checking equality)
Arithmetic is cumbersome
Example: 4-3 != 4+(-3)
Negatives “increment” in wrong
direction!
20
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 0
– 1
– 2
– 3
– 4
– 5
– 6
– 7
0100
+ 1011
1111
0100
– 0011
0001
4
– 3
1
✓
4
+ -3
-7
✗
Sign and Magnitude
CS295
L04: Integers I
Arithmetic is cumbersome
4 – 3 should be 1, as we see on the left
But 4 + -3 should be equivalent, but if we naively add the two together, it doesn’t work
We have to make sure we change all plus-negatives to subtractions
So, how do we solve these problems?
It turns out there’s a really clever other way of interpreting the MSB
Two’s Complement
Let’s fix these problems:
“Flip” negative encodings so incrementing works
21
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 7
– 6
– 5
– 4
– 3
– 2
– 1
– 0
CS295
L04: Integers I
Negative addition should work now
Two’s Complement
Let’s fix these problems:
“Flip” negative encodings so incrementing works
“Shift” negative numbers to eliminate –0
MSB still indicates sign!
This is why we represent one
more negative than positive
number (- to 1)
22
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 8
– 7
– 6
– 5
– 4
– 3
– 2
– 1
CS295
L04: Integers I
We shift negatives so 0 == 0
Two’s Complement Negatives
Accomplished with one neat mathematical trick!
4-bit Examples:
10102 unsigned:
1*23+0*22+1*21+0*20 = 10
10102 two’s complement:
-1*23+0*22+1*21+0*20 = –6
-1 represented as:
11112 = -23+(23 – 1)
MSB makes it super negative, add up
all the other bits to get back up to -1
23
has weight , other bits have usual weights
. . .
b0
bw-1
bw-2
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 8
– 7
– 6
– 5
– 4
– 3
– 2
– 1
Two’s
Complement
CS295
L04: Integers I
Big negative shift!
8 + 2 = 10
-8 + 2 = -6
Why Two’s Complement is So Great
Roughly same number of (+) and (–) numbers
Positive number encodings match unsigned
Simple arithmetic (x + -y = x – y)
Single zero
All zeros encoding = 0
Simple negation procedure:
Get negative representation
of any integer by taking
bitwise complement and
then adding one!
( ~x + 1 == -x )
24
0000
0001
0011
1111
1110
1100
1011
1010
1000
0111
0110
0100
0010
0101
1001
1101
+ 0
+ 1
+ 2
+ 3
+ 4
+ 5
+ 6
+ 7
– 8
– 7
– 6
– 5
– 4
– 3
– 2
– 1
Two’s
Complement
CS295
L04: Integers I
Memorize this trick. It’s very handy
Summary
Bit-level operators allow for fine-grained manipulations of data
Bitwise AND (&), OR (|), and NOT (~) different than logical AND (&&), OR (||), and NOT (!)
Especially useful with bit masks
Choice of encoding scheme is important
Tradeoffs based on size requirements and desired operations
Integers represented using unsigned and two’s complement representations
Limited by fixed bit width
We’ll examine arithmetic operations next lecture
25
CS295
L04: Integers I
Watch out for & vs &&