CSC373/406: Lecture 2 (Integer Representations)

Contents [0/9]

Integers: Tricks with bitwise ops [1/9]

Integers: Unsigned ints [2/9]

Integers: Twos complement ints [3/9]

Integers: Datalab hints [4/9]

Integers: Types [5/9]

Integers: Bits! How Programs are Stored [6/9]

Integers: Characters are just bits! [7/9]

Integers: Show Bytes [8/9]

Integers: Two's Complement [9/9]

Integers: Tricks with bitwise ops [1/9]

   int x = ...;
   int y = ...;
   // what do the following three lines do?
   x = x ^ y;
   y = x ^ y;
   x = x ^ y;

   // what about this?
   int fun (int x, int y, int z) {
     int xtru = (!!x) <<31 >>31;
     int xfls = ~xtru;
     return (xtru & y) | (xfls & z)
   }

   // How about this?
   int xtru = (~!x) + 1;
}

Integers: Unsigned ints [2/9]

Adding binary and hex numbers

unsigned types

   unsigned char x = ...;  // 8 bits
   unsigned int  y = x;    // 32 bits

   unsigned int  x = ...;  
   unsigned char y = x;

Adding unsigned numbers

   unsigned char x = 250;
   unsigned char y1 = x + 5;
   unsigned char y2 = x + 6;

   QUESTION: y1 == 0
   QUESTION: y2 == 0

Adding unsigned numbers

Modular arithmetic

   unsigned char x = ...
   unsigned char y = ...

   unsigned int ix = x;
   unsigned int iy = y;

   FACT: ((unsigned char) (x + y)) == ((ix + iy) % 256)
   FACT: ((unsigned char) (x - y)) == ((ix - iy) % 256)
   FACT: ((unsigned char) (x * y)) == ((ix * iy) % 256)
   FACT: ((unsigned char) (x / y)) == ((ix / iy) % 256) /* if y != 0 */

Detecting unsigned overflow

Multiplication/Division by powers of two

Integers: Twos complement ints [3/9]

Integers: Datalab hints [4/9]

For next Tuesday: bitNor bitXor isNotEqual getByte copyLSB logicalShift bitCount bang leastBitPos tmax

/* 
 * bitNor - ~(x|y) using only ~ and & 
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
  //HINT: deMorgan's law
}
/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 2
 */
int bitXor(int x, int y) {
  //HINT: alternative characterization of xor in notes
}
/* 
 * isNotEqual - return 0 if x == y, and 1 otherwise 
 *   Examples: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int isNotEqual(int x, int y) {
}
/* 
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n) {
}
/* 
 * copyLSB - set all bits of result to least significant bit of x
 *   Example: copyLSB(5) = 0xFFFFFFFF, copyLSB(6) = 0x00000000
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int copyLSB(int x) {
}
/* 
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 1 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 16
 *   Rating: 3 
 */
int logicalShift(int x, int n) {
  // HINT: return ((n==0) ? x : mysolution)
  // To compute mysolution, you can assume that n!=0
  //   Use arithmetic shift, then mask off the top n bits to 0
}
/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
int bitCount(int x) {
  //SOLUTION #1: one bit at a time
  // int m1 = 0x1;
  // int s1 = (x&m1) + ((x>>1)&m1) + ((x>>2)&m1) + ((x>>3)&m1)
  //   + ((x>>4)&m1) + ((x>>5)&m1) + ((x>>6)&m1) + ((x>>7)&m1)
  //   + ((x>>8)&m1) + ((x>>9)&m1) + ((x>>10)&m1) + ((x>>11)&m1)
  //   + ((x>>12)&m1) + ((x>>13)&m1) + ((x>>14)&m1) + ((x>>15)&m1)
  //   + ((x>>16)&m1) + ((x>>17)&m1) + ((x>>18)&m1) + ((x>>19)&m1)
  //   + ((x>>20)&m1) + ((x>>21)&m1) + ((x>>22)&m1) + ((x>>23)&m1)
  //   + ((x>>24)&m1) + ((x>>25)&m1) + ((x>>26)&m1) + ((x>>27)&m1)
  //   + ((x>>28)&m1) + ((x>>29)&m1) + ((x>>30)&m1) + ((x>>31)&m1);
  // return s1;
  // HINT: to do it faster, add the bits in each BYTE in parallel, 
  //       then add the four sums together.
}
/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  // TRICK: x and -x are nonnegative only at 0
}
/* 
 * leastBitPos - return a mask that marks the position of the
 *               least significant 1 bit. If x == 0, return 0
 *   Example: leastBitPos(96) = 0x20
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 4 
 */
int leastBitPos(int x) {
  // TRICK: the only bit set in both x and -x will be the least significant one 
  // +0x02 = 00000010
  // -0x02 = 11111110 = 11111101+1
  // +0x3C = 00111100
  // -0x3C = 11000100 = 11000011+1
}
/* 
 * TMax - return maximum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmax(void) {
}
/* 
 * isNonNegative - return 1 if x >= 0, return 0 otherwise 
 *   Example: isNonNegative(-1) = 0.  isNonNegative(0) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 3
 */
int isNonNegative(int x) {
}
/* 
 * isGreater - if x > y  then return 1, else return 0 
 *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isGreater(int x, int y) {
}
/* 
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n) {
  // HINT: 
  // int bias = x>0 ? 0 : ((1<<n)-1);
  // add in the bias and then shift right
}
/* 
 * absVal - absolute value of x (except returns TMin for TMin)
 *   Example: abs(-1) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 10
 *   Rating: 4
 */
int absVal(int x) {
  //HINT: return (x>=0)?x:-x;
}
/* 
 * addOK - Determine if can compute x+y without overflow
 *   Example: addOK(0x80000000,0x80000000) = 0,
 *            addOK(0x80000000,0x70000000) = 1, 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int addOK(int x, int y) {
}

Integers: Types [5/9]

Primitive types in C include (with size in bytes, using gcc on x86)

declaration  size   values
char   f;     1      -128 to 127
short  c;     2      -32,768 to 32,767
int    a;     4      -2,147,483,648 to 2,147,483,647
long   b;     4      -2,147,483,648 to 2,147,483,647
float  d;     4      -3.4e38 to 3.4e38   //  7 decimal digits of precision
double e;     8      -1.7e308 to 1.7e308 // 15 decimal digits of precision 

int  h[20];  80      // array of 20 int  (20*4==80)
char i[20];  20      // array of 20 char (20*1==20)

sizeof operator tells you how many bytes something takes up

file:sizeof.c [source]

00001: #include <stdio.h>
00002: 
00003: void fn(int x[ ]) {
00004:   printf("In fn\nint array: %d\n", sizeof x);
00005: }
00006: 
00007: int main() {
00008:   int a;
00009:   long b;
00010:   short c;
00011:   float d;
00012:   double e;
00013:   char f;
00014:   int *g;
00015:   int h[20];
00016:   printf("int: %d\nlong: %d\nshort: %d\nfloat: %d\n", 
00017:          sizeof a, sizeof b, sizeof c, sizeof d);
00018:   printf("double: %d\nchar: %d\nint *: %d\nint array: %d\n", 
00019:          sizeof e, sizeof f, sizeof g, sizeof h);
00020:   fn(h);
00021:   return 0;
00022: }
00023:

An array parameter is really a pointer!

Integers: Bits! How Programs are Stored [6/9]

Everything in a computer memory is a bit (0 or a 1)
8 bits = 1 byte
The byte is the smallest addressable chunk of memory on modern machines
Machines are limited in how much memory they can possibly have by their address space size
Example: most PC's are 32-bit machines, which means that there are at most 2^32 bytes of memory on the machine (about 4 GBytes)

Storing programming statements

Every statement in a program is translated (by the compiler) into one or more machine instructions
The possible machine instructions depend on the type of machine used (Intel, Sun, Apple)
On a typical Windows machine with an Intel CPU, each instruction takes up between 1 and 9 bytes
These instructions are stored in contiguous memory somewhere in the address space

Storing data

Each data type in C has its own internal representation
int: 32-bit binary number
long: 32-bit or 64-bit binary number (depends on the machine)
double: we'll discuss its format next week
char: ASCII encoding (or Unicode, which is an extension)

Using printf format strings to look at underlying representations of data

%x will print any piece of data out in hexadecimal
%p will print out a pointer

Example:

#include <stdio.h>

int main( ) {
  int a = 28;
  double b = 33333.555555;
  char c = 'c';

  printf("a: %d %x\nb: %4.1f %x\nc: %d %x\n",
         a, a, b, b, (int) c, c);
}

Conversion between decimal, binary, and hex

In base 10, the nth digit from the right in the number represents the number of 10^n 's in the number

Example: 2538

Digit	Offset from the right	Represents
8	0	8 * 10^0 = 8
3	1	3 * 10^1 = 30
5	2	5 * 10^2 = 500
8	0	2 * 10^3 = 2000

So the number is 8 + 30 + 500 + 2000 = 2538.

Converting from other bases to base 10 can be done in the same way. For example, in binary, each column represents a power of 2.

Example: 1001101

Digit	Offset from the right	Represents
1	0	1 * 2^0 = 1
0	1	0 * 2^1 = 0
1	2	1 * 2^2 = 4
1	3	1 * 2^3 = 8
0	4	0 * 2^4 = 0
0	5	0 * 2^5 = 0
1	6	1 * 2^6 = 64

So the number is 1 + 0 + 4 + 8 + 0 + 0 + 64 = 37

Example of conversion from hex

Base 16
need 16 different "digits": 0-9, A-F (so F represents 15)
Each column in a number represents a power of 16

Example: 0xA203

Digit	Offset from the right	Represents
3	0	3 * 16^0 = 3
0	1	0 * 16^1 = 0
2	2	0 * 16^2 = 512
a	3	10 * 16^3 = 40960

So the number is 3 + 0 + 512 + 40960 = 41475

Integers: Characters are just bits! [7/9]

file:ascii-table.c [source]

00001: #include <stdio.h>
00002: 
00003: int main()
00004: {
00005:   int i;
00006: 
00007:   for (i = 0; i < 128; i++)
00008:     printf("%c:  %d\n", i, i);
00009: }
00010:

The example shows that characters are just numbers.
- After all, everything on a computer is just a bunch of 0's and 1's
Each character is represented by its ascii encoding (a number between 0 and 255)
Printing a number using %c tells printf to treat it like a character

file:ascii-count.c [source]

00001: #include <stdio.h>
00002:  
00003: main()      /* counts digits, white space, others */
00004: {
00005:   int c, i, num_digits[10], num_white, num_other;
00006: 
00007:   num_white = num_other = 0;
00008: 
00009:   for(i = 0; i < 10; i++)   /* initialize */
00010:     num_digits[i] = 0;
00011: 
00012:   while((c = getchar()) != EOF) {
00013:     if (c >= '0' && c <= '9')
00014:       ++num_digits[c-'0'];
00015:     else if (c == ' ' || c == '\n' || c == '\t')
00016:       ++num_white;
00017:     else
00018:       ++num_other;
00019:   }
00020: 
00021:   printf("digits =");
00022:   for(i = 0; i < 10; i++)
00023:     printf(" %d", num_digits[i]);
00024:   printf(", white space = %d, other = %d\n", num_white, num_other);
00025: }
00026:

Integers: Show Bytes [8/9]

file:show-bytes.c [source]

00001: #include <stdio.h>
00002: typedef unsigned char *byte_pointer;
00003: 
00004: void show_bytes(byte_pointer start, int len) {
00005:   int i;
00006:   for (i=0; i<len; i++) {
00007:     printf("%.2x", start[i]); 
00008:     printf(" ");
00009:   }
00010: }
00011: void show_int(int x)       { show_bytes((byte_pointer) &x, sizeof(int)); }
00012: void show_float(float x)   { show_bytes((byte_pointer) &x, sizeof(float)); }
00013: void show_pointer(void *x) { show_bytes((byte_pointer) &x, sizeof(void *)); }
00014: 
00015: void print_binary(int x) {
00016:   int size = (sizeof x) * 8;  // makes this machine-independent
00017:   // 2's complement
00018:   if (x<0) printf("1");
00019:   else printf("0");
00020:   int i;
00021:   int mask = 1;
00022:   for (i=1; i<size-1; i++)
00023:     mask = mask << 1;
00024:   for (i=1; i<size; i++) {
00025:     if (x&mask) printf("1");
00026:     else printf("0");
00027:     mask = mask >> 1;
00028:   }
00029: }
00030:

file:show-bytes-eg.c [source]

00001: #include <stdio.h>
00002: #include <string.h>
00003: 
00004: #include "show-bytes.c"
00005: 
00006: void test_show_bytes(int val)
00007: {
00008:     int ival = val;
00009:     show_int(ival);
00010:     print_binary(ival);
00011:     printf ("\n");
00012: 
00013:     float fval = (float) ival;
00014:     show_float(fval);
00015:     printf ("\n");
00016: 
00017:     int *pval = &ival;
00018:     show_pointer(pval);
00019:     printf ("\n");
00020: }
00021: 
00022: void simple_show()
00023: {
00024:     int val = 0x12345678;
00025:     byte_pointer valp = (byte_pointer) &val;
00026:     show_bytes(valp, 1); /* A. */
00027:     printf ("\n");
00028:     show_bytes(valp, 2); /* B. */
00029:     printf ("\n");
00030:     show_bytes(valp, 3); /* C. */
00031:     printf ("\n");
00032: }
00033: 
00034: void float_eg()
00035: {
00036:     int x = 3490593;
00037:     float f = (float) x;
00038:     show_int(x);
00039:     printf ("\n");
00040:     show_float(f);
00041:     printf ("\n");
00042: }
00043: 
00044: void string_eg()
00045: {
00046:     char *s = "ABCDEF";
00047:     show_bytes((unsigned char *)s, (int) strlen(s)+1); 
00048:     printf ("\n");
00049: }
00050: 
00051: void show_twocomp() 
00052: {
00053:     short int x = 12345; 
00054:     short int mx = -x; 
00055:     
00056:     show_bytes((byte_pointer) &x, sizeof(short int)); 
00057:     printf ("\n");
00058:     show_bytes((byte_pointer) &mx, sizeof(short int)); 
00059:     printf ("\n");
00060: }
00061: 
00062: int main(int argc, char *argv[])
00063: {
00064:     int val = 12345;
00065: 
00066:     if (argc > 1) {
00067:       if (argv[1][0] == '0' && argv[1][1] == 'x')
00068:   sscanf(argv[1]+2, "%x", &val);
00069:       else
00070:   sscanf(argv[1], "%d", &val);
00071:       printf("Calling test_show_bytes\n");
00072:       test_show_bytes(val);
00073:     } else {
00074:       printf("Calling show_twocomp\n");
00075:       show_twocomp();
00076:       printf("Calling simple_show\n");
00077:       simple_show();
00078:       printf("Calling float_eg\n");
00079:       float_eg();
00080:       printf("Calling string_eg\n");
00081:       string_eg();
00082:     }
00083:     return 0;
00084: }
00085:

Integers: Two's Complement [9/9]

file:unsigned1.c [source]

00001: #include <stdio.h>
00002: 
00003: int main() {
00004:   int i;
00005:   int x;
00006:   unsigned int y;
00007: 
00008:   printf("-1 signed and unsigned\n");
00009:   x = -1;
00010:   printf("%d %u\n", x, x);
00011: 
00012: 
00013:   printf("\ngoing up\n");
00014:   x = 1;
00015:   y = 1;
00016:   for (i=0; i<=32; i++) {
00017:     printf("%12d %12u\n", x, y);
00018:     x <<= 1;
00019:     y <<= 1;
00020:   }
00021: 
00022:   printf("\ngoing down\n");
00023:   x = 1<<31;
00024:   y = 1<<31;
00025:   for (i=0; i<=32; i++) {
00026:     printf("%12d %12u\n", x, y);
00027:     x >>= 1;
00028:     y >>= 1;
00029:   }
00030:   return 0;
00031: }
00032:

Revised: 2007/04/05 17:41