程序代写代做代考 compiler algorithm scheme Java Integers II CSE 351 Autumn 2016

Integers II CSE 351 Autumn 2016

Integers II

http://xkcd.com/1953/

CS295
L05: Integers II

Integers
Binary representation of integers
Unsigned and signed
Casting in C
Consequences of finite width representations
Overflow, sign extension
Shifting and arithmetic operations

CS295
L05: Integers II

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…

3
… zero???
Most Significant Bit

CS295
L05: Integers II
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?
4

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
L05: Integers II
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)
5

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
L05: Integers II

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!
6

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
L05: Integers II
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

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
L05: Integers II
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)
8

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
L05: Integers II
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

9
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
L05: Integers II
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 )

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
L05: Integers II
Memorize this trick. It’s very handy

Peer Instruction Question
Take the 4-bit number encoding x = 0b1011
What’s it mean as an unsigned 4-bit integer?
What about signed?

-4
-5
11
-3
We’re lost…
11

CS295
L05: Integers II
Unsigned: 8 + 2 + 1 = 11
Signed = -8 + 2 + 1 = -5

Two’s Complement Arithmetic
The same addition procedure works for both unsigned and two’s complement integers
Simplifies hardware: only one algorithm for addition
Algorithm: simple addition, discard the highest carry bit
Called modular addition: result is sum modulo

4-bit Examples:
12
4
+3 0100
+0011 -4
+3 1100
+0011 4
-3 0100
+1101
=7
=-1 =1

CS295
L05: Integers II
Ask class to help with math
Drop the carry!

Why Does Two’s Complement Work?
For all integers , we want:

Start with an observation: what’s x + ~x?
13
bit representation of –
bit representation of –

(ignoring the carry-out bit)
00000001
+ 11111110

00000010
+ 11111101

11000011
+ 00111100

CS295
L05: Integers II
We can derive the negation trick from earlier
We want an additive inverse property.
X – X = 0

Why Does Two’s Complement Work?
For all integers , we want:

Start with an observation: what’s x + ~x?

So what’s x + ~x + 1
14
bit representation of –
bit representation of –

(ignoring the carry-out bit)
00000001
+ 11111110
11111111

00000010
+ 11111101
11111111

11000011
+ 00111100
11111111

CS295
L05: Integers II
We want an additive inverse property.
X – X = 0

Why Does Two’s Complement Work?
For all integers , we want:

Start with an observation: what’s x + ~x?

So what’s x + ~x + 1 = 0
15
bit representation of –
bit representation of –

(ignoring the carry-out bit)
00000001
+ 11111110
11111111

00000010
+ 11111101
11111111

11000011
+ 00111100
11111111

-x == ~x + 1

CS295
L05: Integers II
We want an additive inverse property.
X – X = 0

UMax – 1

TMax

TMin

–1

–2

0
UMax
TMax
TMax + 1
2’s Complement Range

Unsigned
Range
Signed/Unsigned Conversion Visualized
Two’s Complement Unsigned
Ordering Inversion
Negative Big Positive
16

CS295
L05: Integers II
Tmax = Two’s complement max value
Umax = Unsigned max value

Values To Remember
Unsigned Values
UMin = 0b00…0
=
UMax = 0b11…1
=

Example: Values for
17
Two’s Complement Values
TMin = 0b10…0
=
TMax = 0b01…1
=
= 0b11…1
Decimal Hex
UMax 18,446,744,073,709,551,615 FF FF FF FF FF FF FF FF
TMax 9,223,372,036,854,775,807 7F FF FF FF FF FF FF FF
TMin -9,223,372,036,854,775,808 80 00 00 00 00 00 00 00
-1 -1 FF FF FF FF FF FF FF FF
0 0 00 00 00 00 00 00 00 00

CS295
L05: Integers II
Remember the mathematical and binary forms, not decimal.

In C: Signed vs. Unsigned
Casting
Bits are unchanged, just interpreted differently!
int tx, ty;
unsigned int ux, uy;
Explicit casting
tx = (int) ux;
uy = (unsigned int) ty;
Implicit casting can occur during assignments or function calls
tx = ux;
uy = ty;

CS295
L05: Integers II
These are user-chosen names, there is nothing special about starting your variable name with ‘t’ or ‘u’.

Casting Surprises
Integer literals (constants)
By default, integer constants are considered signed integers
Hex constants already have an explicit binary representation
Use “U” (or “u”) suffix to explicitly force unsigned
Examples: 0U, 4294967259u

Expression Evaluation
When you mixed unsigned and signed in a single expression, then signed values are implicitly cast to unsigned
Including comparison operators <, >, ==, <=, >=
19
!!!

CS295
L05: Integers II
WARNING!
You will mess this up! When it happens suspect this

Unsigned dominates

Casting Surprises
32-bit examples:
TMin = -2,147,483,648, TMax = 2,147,483,647
20
!!!
Left Constant Order Right Constant Interpretation
0
0000 0000 0000 0000 0000 0000 0000 0000 0U
0000 0000 0000 0000 0000 0000 0000 0000
-1
1111 1111 1111 1111 1111 1111 1111 1111 0
0000 0000 0000 0000 0000 0000 0000 0000
-1
1111 1111 1111 1111 1111 1111 1111 1111 0U
0000 0000 0000 0000 0000 0000 0000 0000
2147483647
0111 1111 1111 1111 1111 1111 1111 1111 -2147483648
1000 0000 0000 0000 0000 0000 0000 0000
2147483647U
0111 1111 1111 1111 1111 1111 1111 1111 -2147483648
1000 0000 0000 0000 0000 0000 0000 0000
-1
1111 1111 1111 1111 1111 1111 1111 1111 -2
1111 1111 1111 1111 1111 1111 1111 1110
(unsigned) -1
1111 1111 1111 1111 1111 1111 1111 1111 -2
1111 1111 1111 1111 1111 1111 1111 1110
2147483647
0111 1111 1111 1111 1111 1111 1111 1111 2147483648U
1000 0000 0000 0000 0000 0000 0000 0000
2147483647
0111 1111 1111 1111 1111 1111 1111 1111 (int) 2147483648U
1000 0000 0000 0000 0000 0000 0000 0000

CS295
L05: Integers II
= U
< S > U
> S
< U > S
> U
< U > S

Integers
Binary representation of integers
Unsigned and signed
Casting in C
Consequences of finite width representations
Overflow, sign extension
Shifting and arithmetic operations

CS295
L05: Integers II

Arithmetic Overflow
When a calculation produces a result that can’t be represented in the current encoding scheme
Integer range limited by fixed width
Can occur in both the positive and negative directions

C and Java ignore overflow exceptions
You end up with a bad value in your program and no warning/indication… oops!
22
Bits Unsigned Signed
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 9 -7
1010 10 -6
1011 11 -5
1100 12 -4
1101 13 -3
1110 14 -2
1111 15 -1

CS295
L05: Integers II

Overflow: Unsigned
Addition: drop carry bit ()

Subtraction: borrow ()
23
15
+ 2
17
1
1111
+ 0010
10001

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
1
– 2
-1
15
10001
– 0010
1111
because of
modular arithmetic

CS295
L05: Integers II
Overflow: Two’s Complement
Addition: () + () = () result?

Subtraction: () + () = ()?
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
For signed: overflow if operands have same sign and result’s sign is different
Two’s
Complement
6
+ 3
9
-7
0110
+ 0011
1001
-7
– 3
-10
6
1001
– 0011
0110

CS295
L05: Integers II
Show TMax, TMin

Sign Extension
What happens if you convert a signed integral data type to a larger one?
e.g. char short int long
4-bit 8-bit Example:
Positive Case
Add 0’s?

Negative Case?
25
4-bit: 0010 = +2
8-bit: ????0010 = ?

00000010
+2
✓

CS295
L05: Integers II

Sign Extension
Task: Given a -bit signed integer , convert it to +-bit signed integer with the same value
Rule: Add copies of sign bit
Let be the -th digit of in binary

26
copies of MSB

• • •

original

CS295
L05: Integers II
General algorithm for any number of bits
Formula is complicated, but visually simple

Sign Extension Example
Convert from smaller to larger integral data types
C (and Java) automatically performs sign extension when converting to larger types
27
short int x = 12345;
int ix = (int) x;
short int y = -12345;
int iy = (int) y;

Var Decimal Hex Binary
x 12345 30 39 00110000 00111001
ix 12345 00 00 30 39 00000000 00000000 00110000 00111001
y -12345 CF C7 11001111 11000111
iy -12345 FF FF CF C7 11111111 11111111 11001111 11000111

CS295
L05: Integers II
0x3 = 0b0011
0xC = 0b1100

Integers
Binary representation of integers
Unsigned and signed
Casting in C
Consequences of finite width representations
Overflow, sign extension
Shifting and arithmetic operations

CS295
L05: Integers II

Shift Operations
Left shift (x<>n) bit-vector x by n positions
Throw away (drop) extra bits on right
Logical shift (for unsigned values)
Fill with 0s on left
Arithmetic shift (for signed values)
Replicate most significant bit on left
Maintains sign of x
29

CS295
L05: Integers II
Useful operator when working with bit representations
Especially Lab 1
1001

Shift Operations
Left shift (x<>n)
Logical shift (for unsigned values)
Fill with 0s on left
Arithmetic shift (for signed values)
Replicate most significant bit on left
Notes:
Shifts by n<0 or nw (bit width of x) are undefined In C: behavior of >> is determined by compiler
depends on data type of x (signed/unsigned)
In Java: logical shift is >>> and arithmetic shift is >>
30
x 0010 0010
x<<3 0001 0000 logical: x>>2 0000 1000
arithmetic: x>>2 0000 1000

x 1010 0010
x<<3 0001 0000 logical: x>>2 0010 1000
arithmetic: x>>2 1110 1000

CS295
L05: Integers II
8 bit example
Undefined is BAD, eats your laundry

Shifting Arithmetic?
What are the following computing?
x>>n
0b 0100 >> 1 = 0b 0010
0b 0100 >> 2 = 0b 0001
Divide by 2n
x<> 1 = 0010 (2)
0001 (1) << 2 = 0100 (4) Left Shifting Arithmetic 8-bit Example No difference in left shift operation for unsigned and signed numbers (just manipulates bits) Difference comes during interpretation: x*2n? 32 x = 25; 00011001 = L1=x<<2; 0001100100 = L2=x<<3; 00011001000 = L3=x<<4; 000110010000 = 25 25 100 100 -56 200 -112 144 Signed Unsigned signed overflow unsigned overflow signed overflow CS295 L05: Integers II Right Shifting Arithmetic 8-bit Examples Reminder: C operator >> does logical shift on unsigned values and arithmetic shift on signed values
Logical Shift: x/2n?
33
xu = 240u; 11110000 =

R1u=xu>>3; 00011110000 =

R2u=xu>>5; 0000011110000 =
240

7
rounding (down)

CS295
L05: Integers II
Right Shifting Arithmetic 8-bit Examples
Reminder: C operator >> does logical shift on unsigned values and arithmetic shift on signed values
Arithmetic Shift: x/2n?
34
xs = -16; 11110000 =

R1s=xu>>3; 11111110000 =

R2s=xu>>5; 1111111110000 =
-16

-2

-1
rounding (down)

CS295
L05: Integers II
Peer Instruction Question

Assume we are using 8-bit arithmetic:
x == (unsigned char) x
x >= 128U
x != (x>>2)<<2 x == -x Hint: there are two solutions (x < 128U) && (x > 0x3F)
35
For the following expressions, find a value of signed char x, if there exists one, that makes the expression TRUE. Compare with your neighbor(s)!

CS295
L05: Integers II
All x
X < 0 X where lowest 2 bits are not 00 0 and -128 (0b10000000) X where upper two bits are 0b01 Summary Sign and unsigned variables in C Bit pattern remains the same, just interpreted differently Strange things can happen with our arithmetic when we convert/cast between sign and unsigned numbers Type of variables affects behavior of operators (shifting, comparison) We can only represent so many numbers in bits When we exceed the limits, arithmetic overflow occurs Sign extension tries to preserve value when expanding Shifting is a useful bitwise operator Right shifting can be arithmetic (sign) or logical (0) Can be used in multiplication with constant or bit masking 36 CS295 L05: Integers II Some examples of using shift operators in combination with bitmasks, which you may find helpful for Lab 1. Extract the 2nd most significant byte of an int Extract the sign bit of a signed int Conditionals as Boolean expressions 37 BONUS SLIDES CS295 L05: Integers II Using Shifts and Masks Extract the 2nd most significant byte of an int: First shift, then mask: (x>>16) & 0xFF

Or first mask, then shift: (x & 0xFF0000)>>16
38
0xFF 00000000 00000000 00000000 11111111

(x>>16) & 0xFF 00000000 00000000 00000000 00000010

x>>16 00000000 00000000 00000001 00000010

x 00000001 00000010 00000011 00000100

x & 0xFF0000 00000000 00000010 00000000 00000000

(x&0xFF0000)>>16 00000000 00000000 00000000 00000010

0xFF0000 00000000 11111111 00000000 00000000

x 00000001 00000010 00000011 00000100

CS295
L05: Integers II
Using Shifts and Masks
Extract the sign bit of a signed int:
First shift, then mask: (x>>31) & 0x1
Assuming arithmetic shift here, but this works in either case
Need mask to clear 1s possibly shifted in
39
x 00000001 00000010 00000011 00000100
x>>31 00000000 00000000 00000000 00000000
0x1 00000000 00000000 00000000 00000001
(x>>31) & 0x1 00000000 00000000 00000000 00000000

x 10000001 00000010 00000011 00000100
x>>31 11111111 11111111 11111111 11111111
0x1 00000000 00000000 00000000 00000001
(x>>31) & 0x1 00000000 00000000 00000000 00000001

0
0
1
1

CS295
L05: Integers II
Using Shifts and Masks
Conditionals as Boolean expressions
For int x, what does (x<<31)>>31 do?

Can use in place of conditional:
In C: if(x) {a=y;} else {a=z;} equivalent to a=x?y:z;
a=(((x<<31)>>31)&y) | (((!x<<31)>>31)&z);
40
x=!!123 00000000 00000000 00000000 00000001
x<<31 10000000 00000000 00000000 00000000 (x<<31)>>31 11111111 11111111 11111111 11111111
!x 00000000 00000000 00000000 00000000
!x<<31 00000000 00000000 00000000 00000000 (!x<<31)>>31 00000000 00000000 00000000 00000000

CS295
L05: Integers II
Use !! to force to 0/1

Unsigned Multiplication in C
Standard Multiplication Function
Ignores high order bits
Implements Modular Arithmetic
UMultw(u , v) = u · v mod 2w
41

• • •

u
v
*

• • •
u · v

• • •

True Product:
bits
Operands:
bits
Discard bits:
bits
UMultw(u , v)

• • •

CS295
L05: Integers II

CSE 351 Lecture 6

Multiplication with shift and add
Operation u<

Related Posts