# 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;

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

int xtru = (~!x) + 1;
}
```

 Integers: Unsigned ints [2/9]

`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
*   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 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`

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

• 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`

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 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 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 00002: typedef unsigned char *byte_pointer; 00003: 00004: void show_bytes(byte_pointer start, int len) { 00005: int i; 00006: for (i=0; i> 1; 00028: } 00029: } 00030: ```

 file:show-bytes-eg.c [source]
 ```00001: #include 00002: #include 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 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