HW2 - bitcount

Dealing With Bits

Problem 1

Solve the following base conversion problems. Place the answers in a text file bases.txt.

  1. hexadecimal to decimal
    1.1. 0x1a =
    1.2. 0xff =
    1.3. 0x23 =

  2. decimal to hexadecimal
    2.1. 25 =
    2.2. 36 =
    2.3. 100 =

  3. hexadecimal to binary
    3.1. 0x1b =
    3.2. 0xfc =
    3.3. 0x20 =
    3.4. 0xfcab =

  4. binary to hexadecimal
    4.1. 1111 1010 =
    4.2. 10 1001 1110 =
    4.3. 1010 1111 0011 0000 =
    4.4. 1100 0010 0011 1101 =

  5. binary to decimal
    5.1. 1111 1010 =
    5.2. 10 1001 1110 =
    5.3. 1010 1111 0011 0000 =

  6. decimal to binary
    6.1. 44 =
    6.2. 67 =
    6.3. 33 =

Problem 2

In this assignment, you will write C code to count the number of 0 bits and 1 bits at each bit position in the bytes of a file presented on standard input. Name the file bitcount.c and the executable bitcount.

That is, take each byte of standard input in turn, and for each bit position 0..7 in that byte (with bit 0 being the least-significant / rightmost bit), increment the ones-count if there is a one bit in that position, and a zero-bit otherwise. When you are done processing, report the number of bytes read and the number of 0 and 1 bits at each position.

Run your program over the concatenation of all the files in /usr/bin on your Linux box, using the Bourne shell in the obvious way:

    cat /usr/bin/* | ./bitcount

Questions to answer in your writeup (README.md):

  1. Build your program with -g. How long does your program take to run? What is the processing rate in bytes per second?

  2. Now, run it a second time. Is it faster? If so, why?

  3. Now, build with -O4 to turn on the GCC optimizer. Run it again. How much faster is it?

  4. Do you notice anything interesting about the output? If so, can you explain it?

Example Run

    $ cat /usr/bin/* | time ./bitcount
    cat: /usr/bin/X11: Is a directory
    cat: /usr/bin/idle: No such file or directory
    728456112 bytes
    bit 0:  465180515 zeros,  263275597 ones
    bit 1:  519708242 zeros,  208747870 ones
    bit 2:  488915046 zeros,  239541066 ones
    bit 3:  457717526 zeros,  270738586 ones
    bit 4:  545107040 zeros,  183349072 ones
    bit 5:  494349692 zeros,  234106420 ones
    bit 6:  442305772 zeros,  286150340 ones
    bit 7:  525850717 zeros,  202605395 ones
    1.01user 0.21system 0:01.24elapsed 99%CPU (0avgtext+0avgdata
    1252maxresident)k
    0inputs+0outputs (0major+64minor)pagefaults 0swaps
    $

Coding Style

Please name your program bitcount.c. Your program must finish with an appropriate exit status.

Your program must be formatted according to the Linux kernel coding style https://www.kernel.org/doc/Documentation/CodingStyle, which is basically "K\&R". You will be using "C99", so take advantage of its features.

The code should be as clear and readable as you can make it: the graders and TAs are going to read a lot of programs, and if yours is hard to understand they will just subtract points and move on.

Your program must start with a comment containing a valid copyright line and a comment indicating the function of the program. For example

    /* Copyright (c) 2016 Bart Massey */
    /* Bit Counter */

Each non-trivial function should have a short comment at the top indicating its behavior.

Your program must have a Makefile that will build it using gcc as the C compiler. The default compiler flags must include -std=c99 -Wall -Werror.

Writeup

Your submission must include a writeup in Markdown format http://daringfireball.net/projects/markdown/ in a file named README.md. The writeup should contain your name, a sample run of your program (like the one above), and a description of anything interesting about your program or its development.

Source Control

For this assignment, you are not required to use source control. However, I strongly suggest putting all your project files under source control: it will avoid backup file messes and give you a good history of work. My recommendation is Git: it's what I use.

Submission

You should submit your materials (program, Makefile, writeup, bit conversions) to the course website as a ZIP archive called bitcount.zip. Use the assignment submission interface on the course website to upload your archive.

Rubrics

problem 1: 30%

problem 2:

  • code 40%

  • writeup 20%

  • makefile 10%