Transcript First project

First project
• Create a JApplet with 3 textfields (2 for input and one for the answer),
appropriate labels, and buttons for plus, minus and times.
• Your JApplet will perform binary int computations: +, - and *
• For negative answers, do not show the two’s complement value,
instead, negate it and show the answer in the appropriate textfield with
a minus sign in front.
• See slides which follow regarding two’s complement representation.
Signed binary ints
• There are many possible signed int representations. We discuss 3 here,
including the one your computer uses.
• Signed ints are positive or negative values. So the representation must
include information on the sign of the number. In all 3 representations
we discuss, the high order bit is reserved to indicated the sign:
0=positive, 1=negative. Notice, we have used one bit for the sign, so
the magnitude of the value we can represent in a given number of bits
is decreased by a power of 2.
• Remember the bit on the left is the msb (most significant bit) and the
bit on the right is the lsb (least significant bit), whatever wordsize you
are using.
• 10011000 is 8 bits, a byte. Which is the msb? Which bit is the lsb?
Sign-magnitude
• A simple way to represent signed ints might be to use the msb for the
sign and the rest of the bits for the magnitude.
• 10001010 is 8 bits, with msb=1, so the number is negative. The value
or magnitude is 10, so this is –10.
• 11111111 and 01111111 are respectively the smallest and largest
possible values in 8 bits. What values (in decimal) are they?
• Why is arithmetic difficult to do in the sign-magnitude representation?
• Because of these problems this representation is not used in modern
digital computers.
One’s complement
• This representation has some things in common with sign-magnitude:
All the positive numbers look the same. Again, if the high order bit is
a 0 then the number is positive, and the rest of the bits represent the
value.
• 00101100 is a positive value in 8-bit one’s complement, and would be
the same value in sign-magnitude. What value?
• 11010011 is the negative representation for the same value. Negation
is performed by flipping bits.
• Arithmetic works somewhat in one’s complement with some
limitations and a curious problem. Can you find the problem?
Two’s Complement
•
•
•
•
•
•
•
•
•
•
Your computer uses two’s complement to represent signed int values.
Positive values look the same as in sign-magnitude and one’s complement.
The process of negation (negating positive values to get negative, or negating
negative values to get positive) is performed in two steps, correcting the funny
arithmetic quirk of one’s complement arithmetic.
Negate a value by flipping bits, then adding a 1.
01101101 represents what positive value?
10010010 is the flip-bits, and 10010011 is the negation of that value.
01101101
+10010011
_________
00000000
Two’s Complement
• Arithmetic in two’s complement works, as long as you don’t add two
positives or two negatives together which yield a sum too big for the
wordsize. This would cause a carry into the sign bit, making a positive
sum negative, for example.
• Practice adding some positive and negatives together.
• An extra value. In an 8 bit representation who is 10000000? It looks
like it should be negative, what happens when you flip the bits and add
1?
• In two’s complement, there is always one more negative value than
positive, and in 8 bits, the range is –128…127 and in 16 bits
• -32768…32767
Adding two binary values
• Adding numbers in any base works the same way. If x[] and y[] and
sum[] are arrays of size SIZE filled with values base b then the
following algorithm computes the sum of the values in x, and y. This
algorithm assumes x and y are padded on the left with 0s.
• int tot,carry =0;
• for(int k=0;k<SIZE;k++){
tot=x[k]+y[k]+carry;
sum[k]=tot%b;//b is the base
carry=tot/b;
}
More remarks on your first project
•
•
•
•
•
•
•
•
•
You will get input as two Strings.
You need to get the binary information out of these and put it into int arrays,
remembering to pad the extra space in the array with zeros.
An array is declared in Java like this:
int []x=new int[20];//or whatever size you want
You can declare it and allocate it later so you could make the global
declaration:
int x[];
And in another method, init() or actionPerformed() allocate the array:
x=new int[20];
A complication. String subscripting starts on the left with 0 and goes up to
StringName.length()-1. You will need to flip over or reverse the order of the
bits in the Strings as you copy them into your arrays. Array subscripts go from
0 to arraylength-1
Methods for your project
• Write the following methods:
• Convert: takes a String and returns the int array the way you want it
• Sumup: adds two binary numbers (arrays) and returns the array sum.
Do not call this method add, there already is an important Component
method in Java named add.
• Flipbits: takes an int array parameter and returns the flipped bits
version of the array
• Shift: Shifts the contents of a binary array by one and returns this new
array (the old one*2)
About java methods (functions)
• Java does not support reference parameters. All parameters are value
parameters.
• Java allows a function return type to be int, float, double, int[], or any
classtype or datatype.
• Consider then the syntax for method operation in you first project.
• Suppose you have two int arrays, x and y. To make y be the flipbits of
x, assuming you have a method called flipBits:
• y=flipBits(x);
• Somewhere in this method must appear the statement return with an
array argument.
• Discuss how to do addition, subtraction and multiplication with the
methods suggested on a previous slide.
Fractions
• A “fractional” value f, is one where 0<=f<1. If f<1 in one base, then
obviously it is less than one in every base. The decimal fraction .5 can
be written in binary as .1
• Note that to the right of the “decimal” point, a digit d in position p in
base b represents d*bp, where the first position to the right of the point
is –1. In binary, .1 represents 1*2-1 = 1/2
• It is possible to convert fractions to/from base b to decimal.
Converting Fractions: Decimal to Another
Base
•
•
•
•
•
•
•
•
Consider converting the base 10 fraction .6842 to base two. Recall the binary
fraction .1 =1/2 1/8 in binary is .001 and is equal to the decimal fraction .125
.6842 =.5 +.125 + .0592 = .101 (2) + ?
We could continue in this fashion guessing at the answer and whittling away
but there is a much simpler way.
.6842 (10) = .b1b2b3b4… (2)
Clearly we need values for each bit b in the answer. If we multiply both sides
of the above equation by 2, on the right side the decimal point shifts right 1
position:
2*.6842 (10) = b1 . b2b3b4… (2). 2*.6842= 1.3684 so b1 =1.
Multiply .3684 by 2 to get 0.7368 so b2=0. Continue:
2*.7368= 1.4736 so b3 =1. The next three iterations would give b4 =0, b5 =1
and b6 =1 so our answer so far is .6842 (10) = .101011 (2)
Converting Fractions: Decimal to Another Base
•
•
•
•
.6842 (10) = .101011 (2)
What is the error in this approximation?
How many binary bits should we give in an “accurate” answer?
Can you devise a method to convert fractions in base 10 to any other
base?
• Conversion decimal to binary can be done by repeatedly multiplying
the decimal fraction by 2, peeling off the “bit” that appears each time
to the left of the decimal point and making it the next bit of the answer,
and continuing until you have enough bits.
Example
•
•
•
•
•
•
•
•
.4298 = what in binary?
.4298*2 = 0.9596 so the first bit of the answer is a 0.
.9596*2 = 1.9182 so the second bit is a 1
.9182*2= 1.8364 so the third bit is a 1
.8364*2= 1.6728 so the next bit is also a 1.
You can see that the next bit will be a 1 and the bit after a 0.
So part of the binary fraction is .011110….
How many bits should we try to get to achieve the same precision that
4 decimal digits has? Is there a formal mathematical way of saying it?
Converting Fractions: Decimal to Another Base
• Assuming a Java interface with TextFields named input (a base 10
fraction), baseval (the new base) and output (where the answer should
appear) here is a java code fragment to do fraction conversions:
•
•
•
•
•
String answer=”.”;//start answer with decimal point
double fraction =Double.parseDouble(input.getText());
int base =Integer.parseInt(baseval.getText());
for (int j=0;j<????;j++)//still need to figure out how many digits
{int temp= (int) fraction*base;
int digit= temp<1?0:temp;
•
•
•
fraction= fraction*base-digit;
answer+=digit;}
output.setText(answer);
A java method that manipulates arrays
• Although this example is not exactly useful for your program, it does
show how to write a method that manipulates & returns an array
argument. Suppose an int array values contains a bunch of decimal
values and we are interested only in knowing whether each value is
even or odd. I might want a boolean array of the same size called
parity. My plan might be to put true in a position of parity if that
position of values contains an even int and false if it is odd.
Code & comments
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
//maybe in the global area appear the declarations
int values[];
boolean parity[];
//maybe in init or somewhere else the arrays are allocated:
values=new int[40];
parity =new boolean[40];
//we assume values has been filled, then somewhere or other is the function call
parity=getParity(values);
//somewhere appears the function definition:
boolean [] getParity(int []x){
boolean temp[]=new boolean[x.length];
for(int k=0;k<x.length;k++)
temp[k]=x[k]%2==0;
return temp;}