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]

Storing programming statements

Storing data

Using printf format strings to look at underlying representations of data

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

DigitOffset from the rightRepresents
808 * 10^0 = 8
313 * 10^1 = 30
525 * 10^2 = 500
802 * 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

DigitOffset from the rightRepresents
101 * 2^0 = 1
010 * 2^1 = 0
121 * 2^2 = 4
131 * 2^3 = 8
040 * 2^4 = 0
050 * 2^5 = 0
161 * 2^6 = 64

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

Example of conversion from hex

Example: 0xA203

DigitOffset from the rightRepresents
303 * 16^0 = 3
010 * 16^1 = 0
220 * 16^2 = 512
a310 * 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: 

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