Home
Syllabus
Readings
Assignments
Tests
Due: 5:00pm, Wednesday, September 28. Value: 35 pts. Submit to Sauron.
Download the files test.c and func.c. Your job is to complete the functions in func.c as specified below, subject to the following restrictions.
Only variable declarations,
assignment statements, and return
statements are allowed. No
if statements or loops are allowed!
The only operators you may use are >>,
<<,
~, &, |,
^,
!,
+, and − (unary and binary).
You may also use the assignment operators combined with
the above, such as >>= and
^=.
Feel free
to include numeric constants in your expressions. You may not use
function calls (except to call other functions in
func.c).
You
cannot use
*, /, <, >,
or ==, or any other operators not listed
above.
For variable types and for casting, the only permitted
type is
int;
unsigned is prohibited.
The test.c file defines a main() function that
will automatically test the functions in func.c and report
whether they work correctly. This code does a fairly thorough job of
testing; but even so, passing the tests does not constitute a guarantee
that the function is actually correct. There is no need to modify
this file, and you should not submit it as part of your solution.
I encourage you to complete each function individually. That is, write one function and make sure it works before moving on. You may find, though, that the order in which they are listed is not the easiest order in which to complete them.
int mult10(int n)Returns ten times n. You may assume that
n is positive, and that the result fits into a 32-bit
two's-complement format.
int rotateRight(int n, int dist)Returns the value of rotating
n
around dist bits to the right. By rotate,
I mean that when bits drop out off the right end of the number,
they rotate back around into the left end. You may assume that
dist is between 1 and 31, inclusive.
Example: Suppose our system uses 8-bit ints, and
we call rotateRight(35, 3).
The binary version of 35 is 00100011, and the final 011 is rotated
back around to the top to arrive at 01100100, which is the
binary representation of 100(10).
For this problem, as with all problems in this assignment,
your code may assume
that the computer uses 32-bit ints.
int bitSetGet(int *bits, int index)Here, bits references the first value in an
array representing a packed bit set, where bits[0] holds
bits 0 through 31 (with bit 0 being the 1's bit of
bits[0]), bits[1] holds bits 32 through
63, and so on. Given index, the function should
return bit index of the packed bit set. You may
assume that index is at least 0.
For example, if our bit set represents the set
{2, 5, 7, 35, 36}, then bits
would reference an array with two numbers: The first would be
0xA4 (notice how it has the
22's bit,
25's bit,
and 27's bit set),
and the second would be 0x18
(with the 235 − 32's bit
and 236 − 32's bit set).
If the value of
index passed is 33, then the function should return 0
since the 2's bit of 0x18 is 0.
For this problem, you may use the brackets operator to retrieve an element from the array.
int hasOddBitCount(int n)Returns 1 if the binary representation of n
contains an odd number of 1's, and 0 if it has an even number of
1's. For example, hasOddBitCount(14) should be 1, since
the binary representation of 14 is 1110, which contains three 1's,
and three is odd.
Reember that you may assume that the computer uses 32-bit
ints.
int canFit(int n, int count)Returns 1 if n can be represented using
only count bits. You may
assume that n is positive and that count
is between 1 and 31, inclusive.
For example,
canFit(14, 4) should return 1, since 14 can be
represented using 4 bits (1110 has four bits in it).
Likewise,
canFit(14, 5) should return 1.
But canFit(14, 3) would return 0.
I will grade your assignment based both on correctness and on the
speed of each function, as measured by counting the operations that the
function performs. The assignment operator = does not count as
an operation, but all other operators (including operator-assignments
such as +=) count as a single operation. As a
guide for what is good
(though not necessarily
optimal), let me give you my solutions' counts.
mult10has 3 operations rotateRighthas 7 operations bitSetGethas 4 operations, not including subscripting (but counting the operators inside the brackets) hasOddBitCounthas 11 operations canFithas 2 operations