程序代写案例-ICSI 404-Assignment 1

ICSI 404 – Assignment 1: The Bit and the Word

In this series of programming assignments, you would go through the step-by-step design process of a br>simple computer (along with its Instruction Set Architecture) and develop a software emulator for this
machine. You would then complete the series by developing an assembler that can assemble a simple
program written in using the instruction set to machine code, which is executed by the emulator.
For the first assignment, your job is set up the basis for internal data representation in the CPU, namely
the bits and the word. While Java provides bit-manipulation capabilities using bitwise operators (&, |)
and bit-shifts (<<,>>), those bit manipulations are to be done within some form of an integer (byte,
short, int or long). However, Java’s lack of support for unsigned integer type comes as an impediment to
having full control for our own algorithms for bit-level arithmetic implemented. The next best option is
to use the “boolean” data type, where we can use the “true” value for a “1” and “false” value for a “0”.
(Internally, Java uses a whole byte for storing these two possible values, because a byte is the smallest
storage allocation possible for storing a variable. One can also use a byte-sized integer, which is going to
take the same space, but the handling the exception when any value other than 0 or 1 is set becomes
the programmer’s burden.)
A single bit, by itself, is not very useful. In order to represent values and addresses, we need multiple
bits. For the machine that we are emulating, we will be using a 32-bit value for both addresses and
values. A word is an indexed collection of bits (like an array), originally fitting the size that the machine
“natively” works on. Along the history of computing, a word became 16 bits. A 32-bit collection of bits
was then named as “long-word” (Similarly, 64-bit is “quad-word”). The BitSet class in java.util
package, designed for representing a set using a bit-vector, can be repurposed for our need. It is much
more space-efficient in that it uses only one bit internally for each bit/boolean value stored in an array
of long (64-bit) integers. To satisfy our need for 32 bit/boolean values, just a single-element array
suffices as that single long integer can pack up to a maximum of 64 bit/boolean values. Moreover, most
of the operations we need to perform on our machine’s long-word are easily implemented using the
built-in methods of the BitSet class, often using simple wrappers.
For our 32-bit machine word, the LongWord class implementation must follow these specifications:
1. The LongWord class must be a new class that does not inherit from (i.e., extend) any other class
(i.e., it implicitly extends only the Java Object class).
2. A LongWord object must have a bit-vector (indexed collection of bits) as part of its data field, to be
implemented using the Java BitSet class, storing the 32 bits of the long-word. Treat the 0th bit of
the bit-vector as the least significant and the 31st bit as the most significant bits. For the sake of
preserving consistency across the class, you may not use any other storage mechanism. Do not
forget to import java.util.BitSet in your source code.
3. You must create the API for your class by implementing the following methods:
a) At creation, every bit of a LongWord object must be initialized to “0”. Follow the BitSet class
documentation to figure out anything you need to do in the constructor to ensure this.
b) Override default toString method of Java objects, also being careful not to make use of the
default toString method of the BitSet data field, which only lists the bit-indexes (for which
the boolean/bit value is true/1) in the set notation. Instead, the printable string form should
have all the 32 bits listed as 0/1 with the most significant bit in the leftmost position and the
least significant bit placed at the rightmost. You may like to group them by 4 or 8 bits with a
space in between. This should be followed by a tab (‘\t’) as delimiter and the equivalent 8 hex
digits for the binary pattern prefixed by 0x, indicating that what follows are hex digits. A typical
string representation may look like the following:
1010 1010 1010 1010 1010 1010 1010 1010 0xaaaaaaaa
You must use @Override annotation to make the compiler enforce overriding of toString.
@Override
String toString(); // returns a string of 0's and 1's
// followed by equivalent hex notation
c) Implement the following public bitwise accessors and mutators:
boolean getBit(int i) // Get bit i as a boolean
void setBit(int i) // set bit i (set to true/1)
void clearBit(int i) // clear bit i (reset to false/0)
void toggleBit(int i) // toggles (flips) bit i
d) Implement the following public accessors and mutators for the whole long-word:
int getSigned(); // returns the value of this long-word as an int
long getUnsigned(); // returns the value of this long-word as a long
void set(int value); // set the value of the bits of this long-word
// (used for testing only)
void copy(LongWord other) // copies the values of the bits from
// another long-word into this one
Note that the bit-pattern representing the largest unsigned 32-bit integer has a 1 in the most
significant 31st bit and Java will interpret it as negative, if the integer is left as an int. Thus we
need a long as the return type for getUnsigned.
e) Implement the following public methods for bit shift operations:
LongWord shiftLeftLogical(int amount); // left-shift this long-word by
// amount bits (padding with 0’s), creates a new long-word
LongWord shiftRightLogical(int amount); // right-shift this long-word
// by amount bits (padding with 0’s), creates new long-word
LongWord shiftRightArithmetic(int amount);// right-shift this long-word
// by amount bits (sign-extending), creates a new long-word
f) Implement the following public methods for bitwise logical operations:
LongWord not(); // negate this LongWord, creating another
LongWord and(LongWord other); // and two LongWords, returning a third
LongWord or(LongWord other); // or two LongWords, returning a third
LongWord xor(LongWord other); // xor two LongWords, returning a third
Note that all four of these operations are on the corresponding bit-vector field in the LongWord,
and the BitSet class implementing the bit-vector already has them implemented as its
methods. You are free to decide whether to use them or not.
g) Implement the following public method to check if a long-word has all 0-bits:
boolean isZero() // returns true if all bits are 0’s in this long-word
Unlike what is actually done in hardware, you may use loops to implement the same operation done on
each bit. You may extract the bits as boolean using getBit and invoke normal boolean operators or
use BitSet build-in methods to operate on multiple bits where appropriate. You must validate inputs
where appropriate.
For getSigned and getUnsigned, the wrong way is to convert to a string and then call the method
Integer.parseInt on it. Do not take this route. Instead, use the powers of two: the rightmost bit is
worth 0 or 1. The next bit is worth 0 or 2; the next is 0 or 4, and so on. You could use Math.Pow() for
this, but since it is always multiplying by 2, it is easy to keep a "factor" and iteratively multiply by 2 or
shift bits.
Consider (by hand), we will convert 1010 to integer:
rightmost is 0. 0 * 1 is 0. Add that to a sum (0). Factor is 1*2 = 2.
next is 1. 1 * 2 is 2. Add that to the sum (2). Factor is 2*2 = 4.
next is 0. 0 * 4 is 0. Add that to the sum (2). Factor is 4*2 = 8.
next (and last) is 1. 1 * 8 is 8. Add that to the sum (10). Factor is 8*2 = 16.
Answer is sum (10).
Setting bits should use the same logic, but backwards. Given an integer, you should perform the above
algorithm backwards to determine which bits should be set to make the longword have the input value.
You can also start from the leftmost bit. Think about how to proceed!
Another caution if you intend to convert a BitSet object to long using toLongArray and have
later plans to re-convert to BitSet using valueOf. This may have some very unexpected program
behavior with exceptions being thrown, especially when the long-word contain an all-zero bit-vector.
Because BitSet is designed for representing a set, this implies an empty set with zero cardinality.
Consequently, many iteration over bits keep failing, causing the exceptions.
You must provide a test file (TestLongWord.java) that implements a void runTests method.
Each method of the LongWord class must be tested in TestLongWord.java. These tests can throw
an exception on failure, print expected and actual values or print “pass” or “fail”, for example. The tests
must be adequate to prove that your LongWord class really works. These tests must be independent of
each other, i.e., you do not want one failed test to cause another failed test to occur. Also, there must
be reasonable coverage. You cannot possibly test all 4 billion possible long-words, but you can test a few
representative samples, including special ones such as 0, -1, largest magnitude signed and unsigned
integers, etc. Your main method should call runTests on TestLongWord. There should be output
that allows a TA/grader to determine that the tests pass or fail. They may also have a battery of tests
that they will run.
You must submit buildable .java files for credit.
Rubric Poor OK Good Great
Comments None/Excessive (0) “What” not “Why”,
few (5)
Some “what”
comments or missing
some (7)
Anything not obvious
has reasoning (10)
Variable/Function
naming
Single letters
everywhere (0)
Lots of abbreviations
(5)
Full words most of
the time (8)
Full words,
descriptive (10)
Unit Tests None (0) Partial Coverage
(7)
All methods covered,
needs more cases
(13)
All methods/cases
covered (20)
Accessors/Mutators
/toString
None (0) Some implemented
(5)
All implemented,
some fail (7)
All implemented, all
tests pass (10)
And None(0) Implemented, wrong
(2)
Implemented, correct
(5)
Or None(0) Implemented, wrong
(2)
Implemented, correct
(5)
Not None(0) Implemented, wrong
(2)
Implemented, correct
(5)
Xor None(0) Implemented, wrong
(2)
Implemented, correct
(5)
Left/Right shift None(0) Implemented, wrong
(5)
Implemented, correct
(10)
GetSigned/Unsigned None(0) Implemented, wrong
(5)
Implemented, correct
(10)
Copy/Set None(0) Implemented, wrong
(5)
Implemented, correct
(10)


欢迎咨询51作业君
51作业君 51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: ITCSdaixie