CSC373/406: Lecture 1 (Binary Representations; Logic)

Contents [0/42]

Are You In The Right Room? [1/42]
Overview of Today's Class [2/42]
Admin: Course Overview [3/42]
Admin: Course Objectives [4/42]
Admin: Prerequisites [5/42]
Admin: Expectations [6/42]
Admin: Textbooks [7/42]
Admin: Course Homepage [8/42]
Admin: Mailing List [9/42]
Admin: Assessment [10/42]
Admin: Attendance [11/42]
Admin: Contact Information [12/42]
Labs: Riely373 Server [13/42]
Labs: SSH [14/42]
Labs: GCC [15/42]
Labs: More linux/C/x86 links [16/42]
linux: ls: list the contents of a directory [17/42]
linux: pwd: Display current directory name (print working directory) [18/42]
linux: rm: Delete Files/Directories [19/42]
linux: mv: Rename a file/directory [20/42]
linux: cp: Copy a file [21/42]
linux: mkdir: Create a directory [22/42]
linux: cd: Change the current directory [23/42]
linux: Viewing a File [24/42]
linux: Printing a File [25/42]
linux: Unix online Manual [26/42]
linux: Unix text editors [27/42]
Homework for Thursday [28/42]
C: Compiling C programs [29/42]
C: Displaying binary data [30/42]
C: Hex [31/42]
C: Formatting [32/42]
C: Boolean algebra [33/42]
C: Boolean algebra [34/42]
C: Logic in C [35/42]
C: Logical Operations in C [36/42]
C: Bit-Level Operations in C [37/42]
C: Masks [38/42]
C: Using XOR [39/42]
C: Shift Operations [40/42]
C: Bit Operations [41/42]
Homework for Tuesday [42/42]

Are You In The Right Room? [1/42]

Course: CSC373/406 (Computer Systems I)

Instructor: James Riely

Overview of Today's Class [2/42]

Admin: Course Overview [3/42]

This is a course on computer systems topics, focusing on machine-level programming and architecture and their relevance for application programming. We will discuss:

Admin: Course Objectives [4/42]

By the end of this class you will be a much better programmer.

By the end of this class you will understand how computer hardware works.

By the end of this class you will be ready for

Admin: Prerequisites [5/42]

You need some programming background for this class. This can be fulfilled by any of the following:

We will not program in Java, Python or C++. We will be using C. We will cover necessary C topics as we need them, but I will assume that you already:

Your knowledge of these topics in Java, Python or C++ will easily transfer to C and will be critical to your success in this class.

Admin: Expectations [6/42]

We will be using several unfamiliar tools:

You will work on three interesting (and time consuming) labs.

To succeed in the class you must engage the material actively. You will need to

Time is of the essence! You need to work early and ask questions early.

If you delay, you will be lost in incomprehensible morass!

Admin: Textbooks [7/42]

Required Books

Computer Systems: A Programmers Perspective, Second Edition [Amazon, AddAll]

by Randal E. Bryant and David R. O'Hallaron (Prentice Hall, 2010)

Be sure to get the 2nd edition.

Online companion to the book: http://csapp.cs.cmu.edu/

System Programming with C and Unix [Amazon, AddAll]

by Adam Hoover (Addison-Wesley, 2010)

Online companion to the book: http://www.pearsonhighered.com/educator/product/System-Programming-with-C-and-Unix/9780136067122.page

The chapters covered in 373 are:

We do not cover any of the "optional" sections (indicated with *)

Admin: Course Homepage [8/42]

Course homepage: http://fpl.cs.depaul.edu/jriely/class/373/publish

Admin: Mailing List [9/42]

You must subscribe to the course mailing list. Do it as soon as possible.

http://groups.google.com/group/csc373spring2012

Admin: Assessment [10/42]

There will be weekly quizzes (for in-class students), three labs, a midterm, and a final. The course grade will be computed as follows:

PLuS students may opt to skip weekly quizzes.

Numerical grades correspond to letter grades roughly as follows:

93-100 = A
90-92  = A-
88-89  = B+
83-87  = B
80-82  = B-        
etc...

In-class students must attend class each week in order to receive points for the weekly quiz. There will be no makeup quizzes, but I will drop the lowest two quiz scores; therefore, you may miss up to two classes without affecting your grade.

Quizzes will last five-ten minutes, and will be given immediately before the break. Quizzes will be based on the self-test problems in the text and will cover material from preceding classes, or from the first half of class. (You are expected to the read the material before class.) The first weekly quiz will cover prerequisite material.

Quizzes will be posted for DL students to do at home, but will not be considered in determining grades.

The midterm and final will be cumulative. You must earn a passing grade on the midterm and final to pass the course.

No late labs will be accepted. There will be no make-up exams, make-up quizzes, nor extra credit assignments. If there is an extreme emergency and you must miss an exam, you must notify me in advance and provide documented evidence of the emergency.

Students in DL sections may take the course remotely. They may take the exam at times different from the in class section, usually within a few days. Exact details will be provided on COL closer to the exam date.

DePaul's academic integrity policy

Admin: Attendance [11/42]

You are responsible for understanding the material presented in class.

You are responsible for any announcements made in class or on the class mailing list.

If you are in the DL section or miss class, you should watch the lecture within 24 hours (ie, the day after the in class lecture.)

In-class students must attend class each week in order to receive credit for the quiz.

In-class students must attend the midterm and final exams.

A medical note will be required for an absence from exams. Business trips or vacations are not valid reasons for missing the exams.

Block out these dates now!

Online students can take exams remotely. Online dates will likely include the weekend before the in class date.

Class materials and recorded lectures are available online. Exams are proctored.

Read the policies here:

http://www.cdm.depaul.edu/onlinelearning/Pages/OnlinePolicies.aspx

If you live in Chicago, you can take the exams at the Loop or Suburban campuses. If you live outside the Chicago area, you will need to find a proctor.

Your online section is paired with an on-campus section. These classes are recorded and uploaded into the Course Management system so you can view them within 24 hours of the live class. The first class is 2011/03/27-29. The lecture will be available online the following day.

Admin: Contact Information [12/42]

Instructor:James Riely
Home Page:http://fpl.cs.depaul.edu/jriely
Email:jriely@cs.depaul.edu
Phone:1.312.362.5251
Address: School of Computing, DePaul University
243 South Wabash Avenue
Chicago, IL 60604-2301
Office:CDM 846
Office Hours: Tue/Thu 3:00pm-4:00pm in CDM 846
Class Page:http://fpl.cs.depaul.edu/jriely/class/373/publish
Class Hours: Tue/Thu 1:30-3:00pm in CDM 220 [Section 601]
Online, Anytime [Section 610]

My coordinates:

Contact by phone:

Contact by email:

Labs: Riely373 Server [13/42]

For labs, we will use a server running linux.

The server name is riely373.cdm.depaul.edu. The ip address is 140.192.39.11

In the rest of the notes, I will use the server name riely373 rather than the ip address. You should substitute the ip address when attempting to connect with the server.

In the rest of the notes, I will use the username stu. You should substitute your own username when attempting to connect with the server.

You can access the machine by going to a command line and typing:

ssh stu@riely373.cdm.depaul.edu

Using PuTTY, connect to server riely373.cdm.depaul.edu with username stu. For FileZilla, use port 22.

Labs: SSH [14/42]

To do the homeworks, you will need an ssh client.

For a gui sftp client (all platforms), get FileZilla

Labs: GCC [15/42]

We will use gcc on riely373.

Some of you may wish to run gcc locally on your home computer.

Labs: More linux/C/x86 links [16/42]

More linux/C links

Linux Commands - A practical reference

Nice one page summary of some more advanced commands.

LinuxCMD.org

Tutorial examples organized by functionality.

linux: ls: list the contents of a directory [17/42]

Command: ls

Arguments: Optional list of files and or directory names

Options: -l

Description: Lists the specified files and or directories. For a directory, all its files and directories are listed. If no file or directory is specified, the current directory is assumed.

Example:

$ ls
csc373          mail            nachos-3.4.tar  test
examples        nachos-3.4      new             test.txt

linux: pwd: Display current directory name (print working directory) [18/42]

Example:

$ pwd
/home/prof

linux: rm: Delete Files/Directories [19/42]

Command: rm

Arguments: file list

Options: -i -r

Description: Removes (deletes) the specified files

-i   Ask before removing each file (Good idea since it is not possible to reverse a removal)
-r   Recursively remove directories and subdirectories in
     the list. Files will be removed in these directories
     first and then the directory itself. (Useful but dangerous)]]

Example:

$ rm test.txt 
$ rm -r test

linux: mv: Rename a file/directory [20/42]

Arguments: existing_file new_file

Options: -i

Description: Renames existing_file to have the name new_file -i Prompts if mv would overwrite an existing file.

Example:

$ ls
code             output.c         test.cpp         thrd.c~
file             sample_busy      test.txt
homework2        sample_busy.cpp  thrd
output           test             thrd.c
$ mv output.c input.c
$ ls
code             output           test.cpp         thrd.c~
file             sample_busy      test.txt
homework2        sample_busy.cpp  thrd
input.c          test             thrd.c

linux: cp: Copy a file [21/42]

Arguments: existing_file new_copy

Description: Copy existing_file to the file new_copy. If new_copy doesn't exist, create it. If it does exist, first delete its contents.

If new_copy is a directory, a copy of existing_file is created in directory new_copy with the same file name - existing_file.

Example:

$ cp sample.cpp prog1.cpp

linux: mkdir: Create a directory [22/42]

Arguments: new_subdirectory_name

Description: Create a subdirectory of the current directory

Example:

$ mkdir hw1

linux: cd: Change the current directory [23/42]

Arguments: target_directory

Options:

Description: Change the current directory (working directory) to the specified target_directory. If no target_directory is specified, change to the login/home directory.

Example:

$ cd hw1

The following changes the current directory to the parent directory:

$ cd ..

linux: Viewing a File [24/42]

There are several tools available for viewing files. The most popular command is "less" invoked as follows:

$ less foo

To scroll the contents of a file to the screen, you can use the cat command. This command gets its name from concatenate: it reads its input file name(s) and writes them to the screen. If you give it more than one file name:

$ cat foo bar

then cat will first write foo to the screen and then bar. Redirecting this output to a file (we won't go into redirection here)
like this:

$ cat foo bar > bas

would give you a file named bas whose content is the contents of bar concatenated to foo. This is a good way to add files together.

linux: Printing a File [25/42]

To print a file, you'll need to use ftp or the secure shell client to transfer the file to a PC. You can then print the file as you would any other file on the PC.

linux: Unix online Manual [26/42]

To view the unix online manual, you need to know the exact name of a manual topic; e.g., fork. In some cases you may not know the exact name. You can try the man command with the -k option (for keyword)

$ man -k fork

The output shows all manual topic names in the first column related to the keyword entered (fork).

Once you know the name of the manual page for a topic use the man command again with that specific topic:

$ man fork

linux: Unix text editors [27/42]

To edit your programs, you will need a text editor.

nano is the easiest to use.

Having said that, the most popular editors in UNIX/Linux are vim and emacs. You can learn about vi at

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/Editors/ViIntro.html

and emacs at

http://heather.cs.ucdavis.edu/~matloff/UnixAndC/Editors/Emacs.html

Here is a short primer on emacs. To start emacs type

$emacs

To open a file file.c using emacs, type

$emacs file.c

You can start editing know. When you want to save your file, type

Ctrl-X Ctrl-S (This means pressing the Ctrl key and pressing x and then s, while still pressing the Ctrl key)

To save a file under a different name, type

Ctrl-X Ctrl-W

To exit emacs, type

Ctrl-X Ctrl-C

Here is a short list of important emacs editing commands

To move the cursor forward or backward, type

Ctrl-F or Ctrl-B

respectively.To move the cursor up or down, type

Ctrl-P and Ctrl-N

respectively. To delete a character pointed to by the cursor, type

Ctrl-D

To cut and paste, move the cursor to the first character of the part you want to cut and paste. Then type

Ctrl-SPACE (SPACE is the space bar)

Then move the cursor down to the last character of the part you want to cut. Then type

Ctrl-W

to cut the text. You can then move the cursor to the position where you want to paste, and type

Ctrl-Y

to paste. You can paste the cut text again and again with Ctrl-Y.

You should be able to modify the properties of the VT102 terminal emulator in SSH to customize some of teh key bindings.

For additional info about UNIX/Linux go to Norman Matloff's intro to Unix

Homework for Thursday [28/42]

Datalab (bitNor)

C: Compiling C programs [29/42]

file:hello.c [source]
00001: #include <stdio.h>
00002: 
00003: int main()
00004: {
00005:   printf("hello, world\n");
00006: } 
00007: 

To compile a single file C program in a file named hello.c use the gcc compiler.

$ gcc hello.c -o hello

This compiles the program hello.c, links it with any standard c library routines called (e.g. i/o routines) and produces the executable file named hello.

Now run hello:

$ ./hello

C: Displaying binary data [30/42]

The following unix commands can make some sense of binary data

C: Hex [31/42]

Computer organization is based on the byte

 4 bits == nibble
 8 bits == byte
32 bits == word (32 bit machine)
64 bits == word (64 bit machine)

 ----------------------
 DECIMAL | HEX | BINARY
 --------|-----|-------
       0 |   0 |  0000
       1 |   1 |  0001
       2 |   2 |  0010
       3 |   3 |  0011
         |     |
       4 |   4 |  0100
       5 |   5 |  0101
       6 |   6 |  0110
       7 |   7 |  0111
         |     |
       8 |   8 |  1000
       9 |   9 |  1001
      10 |   A |  1010
      11 |   B |  1011
         |     |
      12 |   C |  1100
      13 |   D |  1101
      14 |   E |  1110
      15 |   F |  1111

C: Formatting [32/42]

file:hello.c [source]
00001: #include <stdio.h>
00002: 
00003: int main()
00004: {
00005:   printf("hello, world\n");
00006: } 
00007: 

file:format.c [source]
00001: #include <stdio.h>
00002: 
00003: int main()
00004: {
00005:   printf ("Characters: %c %c \n", 'a', 65);
00006:   printf ("Characters: %d %d \n", 'a', 65);
00007:   printf ("Decimals: %d %d\n", 1977, 65000000);
00008:   printf ("Preceding with blanks: %10d \n", 1977);
00009:   printf ("Preceding with zeros: %010d \n", 1977);
00010:   printf ("Some different radixes: %d %x %o %#x %#o \n", 
00011:               100, 100, 100, 100, 100);
00012:   printf ("floats: %4.2f %+.0e %E \n", 3.1416, 3.1416, 3.1416);
00013:   printf ("%s \n", "A string");
00014:   int x;
00015:   float y;
00016:   printf("Enter a decimal and a floating point number\n");
00017:   scanf("%d %f", &x, &y);
00018:   printf("You entered %d %lf\n", x, y); 
00019: 
00020:   char s[1];
00021:   printf("Enter a string\n");
00022:   scanf("%s", s);
00023:   printf("You entered %s\n", s); 
00024:   return 0;
00025: }
00026: 

C: Boolean algebra [33/42]

1 and 0 are like true and false

C: Boolean algebra [34/42]

1 and 0 are like true and false

C: Logic in C [35/42]

C: Logical Operations in C [36/42]

C: Bit-Level Operations in C [37/42]

Examples using one byte. The examples show the number in base-2 (binary) notation.

 x   == 01000001
~x   == 10111110

 x   == 00000000
~x   == 11111111

 x   == 01101001
 y   == 01010101
 x&y == 01000001

 x   == 01101001
 y   == 01010101
 x|y == 01111101

 x   == 01101001
 y   == 01010101
 x^y == 00111100

the following hold for any x

 ~(~x) == x

C: Masks [38/42]

the following hold for any x

x & x         == x
x & 00000000  == 00000000
x & 11111111  == x

x | x         == x
x | 00000000  == x
x | 11111111  == 11111111

What about

x & 00001111  == 
x | 00001111  == 

C: Using XOR [39/42]

XOR is important in cryptography

the following hold for any x and y

x ^ x         ==  0
x ^ 00000000  ==  x
x ^ 11111111  == ~x

x ^ y == (~x | ~y) & ~(x & y)
x ^ y == (x & ~y) | (~x & y)

C: Shift Operations [40/42]

Left shift:

 x    == 01100010
 x<<1 == 11000100
 x<<2 == 10001000
 x<<3 == 00010000
 x<<4 == 00100000
 x<<5 == 01000000
 x<<6 == 10000000
 x<<7 == 00000000
 x<<8 == 00000000

Right shift:

        (logical)      (arithmetic)
 x    == 01100010       01100010
 x>>1 == 00110001       00110001
 x>>2 == 00011000       00011000
 x>>3 == 00001100       00001100
 x>>4 == 00000110       00000110
 x>>5 == 00000011       00000011
 x>>6 == 00000001       00000001
 x>>7 == 00000000       00000000
 x>>8 == 00000000       00000000

        (logical)      (arithmetic)
 x    == 11100010       11100010
 x>>1 == 01110001       11110001
 x>>2 == 00111000       11111000
 x>>3 == 00011100       11111100
 x>>4 == 00001110       11111110
 x>>5 == 00000111       11111111
 x>>6 == 00000011       11111111
 x>>7 == 00000001       11111111
 x>>8 == 00000000       11111111

C: Bit Operations [41/42]

file:bitops.c [source]
00001: // shows the effect of various bit operations
00002: #include <stdio.h>
00003: 
00004: #include "show-bytes.c"
00005: int main() {
00006:   int x,y;
00007:   unsigned int z;
00008:   printf("Enter 2 numbers\n");
00009:   scanf("%x %x", &x, &y);
00010:   z = x;
00011:   printf("x in binary is ");
00012:   print_binary(x);
00013:   printf("\ny in binary is ");
00014:   print_binary(y);
00015:   printf("\n\nx & y        = ");
00016:   print_binary(x&y);
00017:   printf("\nx | y        = ");
00018:   print_binary(x|y);
00019:   printf("\nx ^ y        = ");
00020:   print_binary(x^y);
00021:   printf("\n\nx            = ");
00022:   print_binary(x);
00023:   printf("\n~x           = ");
00024:   print_binary(~x);
00025:   printf("\nx<<1         = ");
00026:   print_binary(x << 1);
00027:   printf("\nx<<2         = ");
00028:   print_binary(x << 2);
00029:   printf("\nx>>3         = ");
00030:   print_binary(x>>3);
00031:   printf("\n\nx in decimal    = %d\n", x);
00032:   printf("~x in decimal   = %d\n", ~x);
00033:   printf("x<<1 in decimal = %d\n", x<<1);
00034:   printf("x<<2 in decimal = %d\n", x<<2);
00035:   printf("x>>1 in decimal = %d\n", x>>1);
00036:   printf("\n");
00037:   printf("\nz            = ");
00038:   print_binary(z);
00039:   printf("\n~z           = ");
00040:   print_binary(~z);
00041:   printf("\nz<<1         = ");
00042:   print_binary(z << 1);
00043:   printf("\nz<<2         = ");
00044:   print_binary(z << 2);
00045:   printf("\nz>>3         = ");
00046:   print_binary(z>>3);
00047:   printf("\n\nz in decimal    = %u\n", z);
00048:   printf("~z in decimal   = %u\n", ~z);
00049:   printf("z<<1 in decimal = %u\n", z<<1);
00050:   printf("z<<2 in decimal = %u\n", z<<2);
00051:   printf("z>>1 in decimal = %u\n", z>>1);
00052:   printf("\n");
00053:   return 0;
00054: }
00055: 

Homework for Tuesday [42/42]

Datalab (bitXor)


Revised: 2008/03/17 13:01