CS61C Spring 2014 Homework 1

Due Sunday, February 2, 2014 @ 11:59pm

Updates

1/26 @ 4:00PM - Usage of string.h is forbidden for Q3.
1/31 @ 12:00AM - x in Q2a is only one bit wide.

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 hw1.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
`0b11111000`
`0b00000111`
`0x0E`
`0xFC`
`35`
`-35`
`64`
`-64`

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(~).

Let x be the input. Fill in the following blanks with either 0, 1, x, or x̅ (NOT x):

x & 0 = ___ x | 0 = ___ x ^ 0 = ___
x & 1 = ___ x | 1 = ___ x ^ 1 = ___
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.

Write a C command that will turn on the read permission for User and Other. Use a hexadecimal constant.
Write a C command that will change the execute permission for Group and Other. Use an octal constant.
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 is_binary_palindrome() in hw1.c that returns 1 if the binary representation of the unsinged integer passed to it is a palindrome, ignoring leading zeros, and 0 otherwise. For instance, the number 27 = 0b11011 is a palindrome, but 4 = 0b100 is not.

	#include <stdio.h>
	#define YES ("a palindrome")
	#define NO ("NOT a palindrome")
	#define CHECK(X) (is_binary_palindrome(X) ? YES : NO)

	int is_binary_palindrome(unsigned int n);

	int main(int argc, char *argv[]) {
	    const char testStr[] = "Program thinks %d is %s, should be %s\n";
	    printf (testStr, 0, CHECK(0) , YES);
	    printf (testStr, 11, CHECK(11), NO);
	    printf (testStr, 2863289685u, CHECK(2863289685u), YES);
	    printf (testStr, 268435456, CHECK(268435456), NO);
	    printf (testStr, 9, CHECK(9), YES);
	    return 0;
	}

	/** Returns 1 iff the binary numeral representing N is a palindrome.
	 *  Ignores leading 0s. */
	int is_binary_palindrome(unsigned int n) {
	}

Problem 4: Command-line arguments

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

	# ./hw1 18
	0

	# ./hw1 255
	1

	# ./hw1 10 20
	too many arguments!

	# ./hw1
	[the same result as from Problem 3]

Edit your hw1.c to include this functionality.

You may assume that the single argument will always be an integer in the range from 0 to 2³¹-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).


`x & 0 = ___`	`x \| 0 = ___`	`x ^ 0 = ___`
`x & 1 = ___`	`x \| 1 = ___`	`x ^ 1 = ___`