CS61C Spring 2013 Homework 1

TA: Paul Ruan

Due Sunday, February 3, 2013 @ 11:59pm

Updates

Goals

This assignment covers a range of topics related to C and number representation. It is also intended to get you to start writing C code on your own.

Submission

Submit your solution by creating a directory named hw1 that contains files named hw1.txt and paircount.c. Please use the provided format in hw1.txt. File names are case-sensitive and the submission program will not accept your submission if your file names differ at all from those specified. From within that directory, type submit hw1. Partners are not allowed on this assignment.

Copy the contents of ~cs61c/hw/01 to a suitable location in your home directory to obtain files you will want for this homework.

	$  cp -r ~cs61c/hw/01/ ~/hw1 

Exercises

Problem 1: Number representation

Assume we are dealing with 8 bit numbers for this problem. Fill in the following table according to the representation given by the column header. If you are given binary or hexadecimal, give the decimal value interpreted under the given representation. If you are given a decimal value, convert it to binary under the given representation and write your answer in hexadecimal. Put "n/a" if the value cannot be converted. Put your answers in hw1.txt.

  unsigned sign & magnitude one's complement two's complement
0b11111100     
0b00000011
    
0x0D     
0xFD     
27     
-27     
128     
-128     

Problem 2: C bitwise operators and masks

Put your answers to the following questions in hw1.txt

Note: If you are unfamiliar with or need to review the truth tables for the standard 2-input logic gates, just Google or Wikipedia 'logic gates'.

C provides bitwise commands for AND(&), OR(|), XOR(^), and NOT(~).

  1. Let x be the input. Fill in the following blanks with either 0, 1, x, or (NOT x):
     
      x & 0 = ___   x | 0 = ___   x ^ 0 = ___
      x & 1 = ___   x | 1 = ___   x ^ 1 = ___
     
  2. Based on your responses, look at the columns (grouped by operation) above. Which operation would be useful for
    1. turning bits OFF?
    2. turning bits ON?
    3. flipping bits?

Often we will use what are known as 'bitmasks' (or just 'masks'), which are binary constants that we use to perform bitwise operations with to produce desired changes in the bits of numbers.
For example, file permissions in UNIX consists of 9 bits - read, write, and execute for User, Group, and Other (from left to right: rwxrwxrwx). Let f be a variable holding the file permissions of a file of interest in its least significant 9 bits. We wish to leave the other bits of f unchanged.

Note: Because we have not specified the data type of f, you don't know how long the masks need to be. Constants are typically extended with zeros. Here the NOT operator can come in handy for generating leading 1's.

  1. Write a C command that will turn on the read permission for User and Other. Use a hexadecimal constant.
  2. Write a C command that will change the execute permission for Group and Other. Use an octal constant.
  3. Write a C command to remove both the write and execute permissions for Other. Use a decimal constant.

Problem 3: C Coding

Write a function pairCount() in paircount.c that returns the number of occurrences of "11" in the binary representation of its unsigned integer argument. For instance, the number 183 is 0b10110111 and there are three occurrences of "11".

	#include <stdio.h>

	int pairCount(unsigned int n);

	int main(int argc, char *argv[]) {
	    const char testStr[] = "# pairs in base 2 of %u = %d, should be %d\n";
	    printf (testStr, 0, pairCount (0), 0);
	    printf (testStr, 11, pairCount (11), 1);
	    printf (testStr, 2863377066u, pairCount (2863377066u), 2);
	    printf (testStr, 268435456, pairCount (268435456), 0);
	    printf (testStr, 4294705151u, pairCount (4294705151u), 29);
	    return 0;
	}

	int pairCount(unsigned int n) {
	}

Problem 4: Command-line arguments

You have decided that you want your paircount program above to work from the command-line (see K&R Section 5.10), as follows:

	# ./paircount 17
	0

	# ./paircount 255
	7

	# ./paircount 10 20
	too many arguments!

	# ./paircount
	[the same result as from Problem 3]
Edit your paircount.c to include this functionality.

You may assume that the single argument will always be an integer in the range from 0 to 231-1. You will find the function atoi helpful.

Extra for experts (not worth any points): Implement this exercise without using the library function atoi (or something comparable).