Assumptions: Assume UB addition using 4 bits.
Solution: 1001.
Comments: You could assume other representations such as 1C, 2C, etc.
The point is to indicate which representation system you're
working in.
Solutions:
Binary: 1100 1010 1111 1110
Octal: 1453768
You can get the octal representation by taking the binary solution
in grouping in 3 bits, starting at the right.
1 100 101 011 111 110
To answer this, you should initially forget about the negative sign.
You'll run into a problem if you deal with it now (in particular, you
may end up convering -6 to 2C and .125 to UB, and then put them together,
which wouldn't make sense.
So, we follow the usual steps:
To get the fraction part, it's useful to know that
2-1 = .5, 2-2 = .25,
2-3 = .125.
The algorithm runs as follows. To convert x (a number
less than 1 written in base 10) to binary, do:
It's useful to indicate the number of bits or the bit subscripts
to show you know how many bits there are.
In other words, attempt to subtract .5, then .25, then .125. Repeat
until you have converted the number. The bad news is that some numbers
infinitely repeat, so you'd have to stop the process at some point.
This involves moving the radix point so that the integer part is 1.
A convenient way to do this for positive numbers is to subtract 1,
then convert to binary, then flip the MSb.
1 | 1000 0001 | 1000 1000 0000 0000 0000 000
You can either write out all the bits, separated by a bar, or
write them on separate lines, as in:
where --0-- would indicate the remaining bits are 0 (and --1--
would indicate the remaining bits are 1).
The exponent (b30-23) is all 1's.
The fraction (b22-0) is NOT all 0's.
Note: you should indicate which bits (or how many bits) the exponent
and fraction contain.
Since 1.0 x 2-126 is the smallest normalized number,
and the number above is even smaller (it's helpful that the above number
is written in scientific notation), then you know it's denormalized.
The steps for handling this are a little different than for normalzied
numbers (and easier, assuming the number is written in scientific notation).
Unlike normalized numbers written in IEEE 754, there's no hidden
1. Also, notice the exponent is all 0's (which is what it should
be for normalized numbers)..
This requires increasing the exponent by 4, thus shifting the radix
point to the left by 4 to compensate.
The number of significant bits is 23 minus the number of leading
zeroes in the fraction. There are three leading 0's (they are
the leftmost bits in the fraction). Thus, 23-3 = 20 significant bits.
You might quesion whether how "significant" they are. After all,
if you type 3 in a calculator, you get the precision the calculator
gives provides. In other words, there's no way to tell specify how
many significant bits you want.
So when you're asked how many significant bits a number has,
just assume that it has been recorded to that precision even if
in reality it hasn't (because there's no way to know that information
anyway, since it's not recorded in the representation).
Answer: Excess (or bias) is 127 (Note: this is a positive value)
Answer: Exponent is -126. (Note: this is a negative value)
Answer: 1.0 x 2-126
Address Value
+-------------+------------+
| 1000 | 1011 1110 | (be)
+-------------+------------+
| 1001 | 1101 1010 | (da)
+-------------+------------+
| 1002 | 1110 1111 | (fe)
+-------------+------------+
| 1003 | 1100 1010 | (ca)
+-------------+------------+
Now that I think of it, writing in binary AND hex would be a good idea. That way, if you make a mistake in binary, it would be easier to tell what went wrong.
A mnemonic is "Kinky Monkeys Give/get Tail", which corresponds to Kilo, Mega, Giga, Tera, which are 210, 220, 230, 240, respectively.
Answer: When you type characters in a text editor, it
gets translated to the ASCII code. Thus '1', '0', '0', '0'
are written in the file as 0x31, 0x30, 0x30, 0x30 (or
more properly, 0011 0001 0011 0000 0011 0000 0011 0000).
You have written 4 bytes into the file, not 4 bits.
However, ASCII files are considered a special case of binary
files (where each byte uses the 7-bit ASCII code).
Answer: If the file was written on a machine that did not have the same endianness as your machine, you may have the bytes reversed.
Answer: This is a trick question. Since ASCII characters
are stored as individual bytes, as long as you are reading in
ASCII, it should not have a problem.
If you want to think of potential problems, one possibility
is that you are using Java, which expects characters to be
represented as Unicode.
Answer: You don't need to know much Java to answer this question. Java expects characters in Unicode, which uses two-bytes to represent each character. Since the file is ASCII, it's not compatible. (However, Java allows you to read one byte at a time, and converting from one byte to Unicode isn't too bad.)
Answer: This problem actually occurred when I programming in Java. I couldn't figure out what was going on. Then I realized that I was expecting Java to process numbers written ASCII format, while Java expected a 4-byte 2C encoding (i.e., the file stores a number like -20 as a dash, the character '2', and the character '0'), while Java expects the number to be stored as 4 byte 2C.
For files you've written in a text editor, your output matches xxd's output. For files like a.out, your hexdump produces strange output that doesn't match xxd's output. Based on information in the previous paragraph, what did you do wrong?
Answer: For many people's projects, a key step involved
converting the char's ASCII code to int format. Some people expected
that the char would be treated as if it were unsigned, and thus
zero-extended when converted to an int.
Unfortunately, converting a char to an int causes the byte to be
sign-extended. That is, the most significant bit is copied to the
upper bits. Thus, the result of casting a character with its MSb as
1 is a negative number, and this can produce incorrect answers when
trying to represent as two characters (written to resemble hex).
This is not usually a problem for ASCII characters because the
most significant bit is 0, thus sign extenstion is the same as
zero extenstion.
Answer:
bool isPowerOfTwo( unsigned int num )
{
for ( int i = 0 ; i < 32 ; i++ )
{
unsigned int mask = 1 << i ;
if ( num == mask )
return true ;
}
return false ;
}
The idea is to generate a mask that is a power of two and compare
it to the number passed in.
Answer:
bool isNaN( float f )
{
// Convert pointer to float to pointer to int
int *p1 = reinterpret_cast<int *>( & f ) ;
unsiged int expMask = 0xff000000 ; // Create 8 1's
expMask >>= 1 ; // shift right by 1
if ( expMask & *p1 != expMask ) // check mask
return false ;
unsiged int fracMask = 0x00ffffffff ; // Create 24 1's
fracMask >>= 1 ; // shift right by 1 to create 23 1's
// Check if the fraction is non-zero
return fracMask & *p1 ;
}
In this case, the tricky part is that bitwise/bitshift operators
don't work on a float values. Unfortunately, you can't simply cast to
convert from float to int (the bits change when you cast float to
int). You have to do the trick shown above (convert pointer types).
Answer:
Also note that in C, you would do a standard cast. C++ recommends
labeling the kind of cast you do.
int num = * reinterpret_cast<int *>( & f ) ;
It's similar to the first line of useful code in the previous
example. In this case, reinterpret the point from an float *
pointer to an int * pointer. Dereference it to get the
int. Notice that dereferencing does NOT change the bits
(neither does reinterpret casting).
Answer: Poor Drool Kitty is confused. She's incorrect.
Basically casting 9 to a char will give you the ASCII code 9
(i.e. 0000 1001), which does not correspond to the ASCII code for '9'
(which is 0011 1001).
(By the way, the real "Drool Kitty" is a female cat, that "belongs"
to an ex-UMD student, who is now a graduate student at University
of Texas---for a while, I used to say it was a "he", until I discovered
the Drool Kitty webpage).
You might wonder why casting fails from char to int. One answer
is: the developers of C chose to define casting from char to int
in that way. It's not unreasonable to say that, either. Just
because you find it doesn't do what you'd like it to do, doesn't
mean they didn't have a good reason to do it the way they did.
I often find students who want a language to behave in a reasonable
(i.e., EASY) way. And they tend to remember (incorrectly) the language
behaving in a certain way (incorrectly). This is why it's rather
critical to OWN a book or KNOW a good website for looking up C++ or C
information. Too many people say "I haven't programmed in C++ in
a year, and I've forgotten everything". I'm afraid that won't cut
it at a job. You've got to learn how to pick things up again by
reading a book, or your old code, or your old notes, or SOMETHING!
OK, rant off.
The reason the C designers chose to define casting the way they did
is because they consider char not only to be a character, but also as
a one byte int. Thus, to cast an intchar, is
similar to casting an int to a short (although a short
usually has two bytes). It chops off the upper bytes of the int.
To convert, you can just add 9 to the character '0'. This may
require static casting the result. C has the following rule: when
adding two numbers of different sizes but same type, make a temporary
copy of the number of the smaller type, and either sign-extend (for
signed int) or zero-extend (for unsigned) to the number of bytes of
the larger type. Thus, adding 9 to '0' may result in a 4-byte answer
since 9 is typically considered an int.
Unlike C++, C allows you to freely change between int and char,
without warnings. As a programmer, you should know that this is
occurring, even if the compiler doesn't alert you to it.
Use this instruction (and additional instructions) to load the following 32 bit value 0xcafebabe. Assume that you can write immediate values in hex.
Answer:
Because 0xbabe has its MSb equal to 1, this will sign
extend, and cause the result of the addition to mess up the upper
16 bits.
In effect the addition looks like:
Yes, you could use addiu (add immediate unsigned), which
behaves in the same way, instead of ori. However, the book
postpones this instruction until later.
lui $r1, 0xcafe # Load upper 16 bits with 0xcafe
ori $r1, $r1, 0xbabe # Load lower 16 bits with 0xbabe
Notice that we use ori (which is bitwise OR with an immediate
value) instead of addi. addi does signed addition.
Thus, it assumes the immediate value (which uses 16 bits) is signed.
To add a signed 16 bit 2C representation to a 32 bit representation
(located in the register), the CPU sign-extends the 16 bit 2C to a
32 bit 2C then adds.
1100 1010 1110 1111 0000 0000 0000 0000 (register 1)
1111 1111 1111 1111 1011 1010 1011 1110 (sign extended 0xbabe)
---------------------------------------
1100 1010 1110 1110 1011 1010 1011 1110 (result of adding)
This is NOT the result you want. However, if you do bitwise
or with ori, you get the desired answer. ori
is a logical operator. When it extends the immediate from 16 bits
to 32 bits, it zero-extends it. The assumption is that logical
operations work with bits, not with signed numbers, thus it
zero-extends instead of sign-extends.
0xcafebabe, of course. Endianness doesnt matter when you are loading
into a register. Why on earth would you want to write it as
0xbebafeca. Recall that endianness is a way of breaking up a
multi-byte quantity into bytes so it can be stored as individual
bytes in memory or in a file.
Even when it's stored in memory (in any endianness), the endianness
tells you which byte is most significant. Thus, in any endianness,
0xca would be the MSByte, which means it should be the uppermost byte
of a register.
No, this can't be done in a single instruction (unless you have no
other instuctions). Some bits are required for the opcode (even if
this is just 1 bit). You might wonder if addi allows you
to load an arbitrary 32 bit value into a register. The answer is
no. The immediate value is 16 bits long, which can be sign-extended
to 32 bits.
Thus, you can only represent sign-extended 16 bit values (where
the upper bits are either all 0's or all 1's).
And yes, it's considered cheating to assume that the register
you're adding it to has an arbitrary value. You have to put
a meaningful value into that register first.
Answer: 26 bits. The answer assumes you have a 6 bit opcode which is
standard for MIPS. So, 32-6 = 26 bits.
Since you were asked to add a new instruction (as opposed to
remove other instructions, which might allow you to decrease the size
of the opcode), assuming 6 bits for the opcode is a reasonable
assumption.
The only potential problem is: what if all opcodes have been used
up (that is all 26 possible opcodes are being used for
legitimate MIPS instructions)?
Either assume it hasn't been used up, or make a 7-bit opcode. The
point of the question is to see if you can reason about MIPS given
what little you know.
Answer:
BEFORE
------
bge $r1, $r2, LABEL # branch if $r1 >= $r2
AFTER
-----
slt $r3, $r1, $r2 # if $r1 >= $r2, then $r3 will be 0 (false)
beq $r3, $r0, LABEL # branch if previous condition was false
Notice this rewriting requires an additional register. Clearly,
the MIPS designer must have felt that using an additional register
is not a problem. With 32 registers to use, you can see why.
(If you only had, say, 4 registers, you might decide that a bge
instruction is better, because it doesn't need a temporary register).
000000 00111 00011 0000 0000 0000 1100 ------ ----- ----- ------------------- (1) (2) (3) (4)For the above,