Lecture 6 Integer Representation in Computer Systems

• In CSCI 1120, integer representation topics included one's complement, two's complement, signed vs. unsigned integers, integer ranges, and addition/multiplication.
• CSCI 2122 focuses on manipulating integers, covering why systems use two's complement, considerations for mixing signed/unsigned integers, mixing integers of different sizes, and unpacking/packing integers.

Integers in Programming

• Most languages offer various integer types.
• Integer sizes in C depend on the platform.
• char is at least 1 byte.
• short is at least 2 bytes.
• int matches the machine's word size.
• long is at least 4 bytes.
• long long is at least 8 bytes.
• Some systems allow int, long, and long long to be the same size.

Determining Integer Size

• The sizeof operator determines the size of a type.
• It takes either a type or a value as input.
• It returns the number of bytes the type or value occupies.
• It is used during memory allocation.
• On Timberlea: char = 1 byte, short = 2 bytes,int = 4 bytes, long = 8 bytes.

Importance of Integer Manipulation

• Programs must input/output binary data and integers.
• Programs interact with hardware like graphics cards.
• Programs translate binary data between different hardware/software.
• Programs use integers in data structures like bitmaps.
• Programs implement high-level numerical packages from low-level integers.

Unsigned Integers Review (n-bit integer)

• Range: 0 to 2^n - 1
• A value will be b(n-1)2^(n-1) + b(n-2)2^(n-2) +...+b(1)2^1+b(0)2^0 , where bi is the ith bit.
• Addition uses bitwise operations with carry.
• Subtraction: converts to addition using the negation of 'y' plus 1: x - y becomes x + ~y + 1.

Two's Complement Examples (8-bit integers)

• To determine the representation of -1: 1 = 00000001, -1 = ~1 + 1 = ~00000001 + 00000001 = 11111110 + 00000001 = 11111111 = 0xff
• To determine the representation of -(-1): -1 = 11111111, -(-1) = ~-1 + 1 = ~11111111 + 00000001 = 00000000 + 00000001 = 00000001 = 0x01
• To determine the representation of -0: 0 = 00000000, -0 = ~0 + 1 = ~00000000 + 00000001 = 11111111 + 00000001 = 00000000 = 0x00
• To determine the representation of 127 + 1: 127 = 01111111 = 0x7f, 127 + 1 = 01111111 + 00000001 = 10000000 = -128 = 0x80

Why Use Two's Complement?

• Although, other signed integer representations include one's complement and Signed-Magnitude, two's complement has advantages.
• The above methods have two representations for 0
• CPUs can use the same operations for both signed and unsigned integers with two's complement.
• Operations are the same, except for expansion when copying from a smaller to a larger type.
• All modern CPUs use two's complement.

Problems

• Given an n-bit signed integer X where n isn't 8, 16, 32, or 64, determine if X is negative or positive.
• Without using '<', determine if X < Y and write a C function for this.
• Write functions for equal, not_equal, less_than_or_equal, greater_than_or_equal, and greater_than.

Casting Integers

• What happens when assigning an integer from a smaller to a larger type, or vice versa?
• Also, what results from assigning a signed integer to an unsigned integer or vice versa?

Integer Truncation

• Assigning a larger integral type value to a smaller integral type may truncate the value.
• When assigning an n-bit integer to an m-bit integer type where n > m, the n-m most significant bits are dropped and only the 'm' least significant bits are considered.

Integer Expansion (Unsigned)

• When assigning a value from a smaller integral type to a larger one, the unused bits turn into zeroes.
• Assigning from an n-bit integer to an m-bit integer where m > n, the 'm-n' most significant bits are 0.

Integer Expansion (Signed)

• Assigning from a smaller integral type to a larger type, the unused bits are set to the sign bit (sign-extension).
• Process: Assigning an n-bit integer to an m-bit integer type (m > n), the m-n most significant bits match the sign bit.
• This is sign-extension.

Integer Conversion

• Assigning a signed integral type value to an unsigned type simply copies the value.

Casting Surprises: 2'sC to Unsigned

• Short x = -9876; unsigned short ux = (unsigned short) x;
• printf("x = %d, ux = %u\n", x, ux); prints x = -9876, ux = ?
• The bit-pattern of +9876 in 16 bits is 0010 0110 1001 0100.
• -9876 is 1101 1001 0110 1100.
• Interpreting -9876's bit-pattern as an unsigned binary gives 55660.

Casting Surprises: Unsigned to 2'sC

• uint32_t ux = ULONG_MAX;
• int32_t x = (int) ux;
• printf("ux = %u, x = %d", ux, x);
• Prints ux = 4294967295, x = ...

Casting Surprises Takeaways

• Mixing signed and unsigned values in an expression implicitly casts signed values to unsigned.
• This includes comparison (<, >, ==, <=, >=).
• -1 < 0U results in -1 being cast as unsigned.
• A past slide shows a negative one will have a bit-pattern corresponding to ULONG_MAX
• 2147483647U > -2147483647-1) RHS casts to unsigned for the bit pattern 1...31zeros... → 2^31
• Hence the above evaluates to false.
• 2147483647 > (int) 2147483647U
• The right-hand side is treated as signed
• A right Hand side with a bit patter of -1, the above expression evaluates to to True.

Pitfalls of Unsigned Integers

• Consider the following code:

int sum(int *values, unsigned int length) {
    int s = 0;
    for (int i = 0; i <= length - 1; i++) {
        s += values[i];
    }
    return s;
}

• If length is 0, length - 1 becomes a large number (4 billion), which can cause a crash.
• Solution: Use i < length as bound.

unsigned int foo(char *x) { ... }

char *foomax(char *x, char *y) {
    if (foo(x) - foo(y) > 0) {
        return x;
    } else {
        return y;
    }
}

• The code demonstrates the problems that can occur when using unsigned integers. The expression turns what may intuitively seem negative to unsigned integers, and thus positive.
• Could write expression foox(x) > foo(y)

Why Not Always Use 2's Complement?

• Java adopted this approach to avoid the discussed pitfalls.
• Drawbacks: lose half the integer range when negative numbers aren't needed, many hardware devices depend on unsigned integers (SSDs), need more complex code for signed integers where unsigned are appropriate, and most system integers are unsigned.

Problem: Decomposing an Integer (Little Endian)

void decompose(int x, char *bytes) {
    for (int i = 0; i < 4; i++) {
        bytes[i] = x;
        x = x >> 8;
    }
}

• The code takes a 4-byte integer and turns the values into its 4 constituent bytes
• It demonstrates accessing each byte by shifting and assigning.

Application: Unpacking and Packing Integers

• Integer representation is optimized for speed, not space.
• E.g. a 64-bit integer with value 1 consumes a lot of space: 00000...0001
• Space-efficient and Computation efficiency requires unpacking/packing operations.
• Unpacking: converts a value from space-efficient to computation-efficient format
• Packing: converts a value from computation-efficient to space-efficient format

Unpacking

• Unpacking translates from source to destination with the following considerations:
• Source of n-bit integer where n may not be 8, 16, 32, or 64 bits
• Destination of m-bit integer with m > n (typical 8, 16, 32, or 64 bits)
• Check if the integer is signed or unsigned (two's complement).
• If source is smaller, the integer will need to be expanded
• If source is larger, the integer will need to be truncated.
• Little-endian: unpack integer least-significant to most-significant bit.
• Big-endian: unpack integer most-significant to least-significant bit.

Problem: Unpack an Integer

• Using an input of long long unpack_signed(char *buffer, int n):
• Where the parameters: bytes that contain a little Endian value, the amount of bits
• Write an algorithm to return a long long integer with a signed value

long long unpack_signed(char *buffer, int n) {
    long long result = 0; /* assume positive int */
    if (test(buffer[(n - 1) / 8], (n - 1) % 8)) {
        result = ~result;
    }

    /* assume n <= 64 */
    for (int i = 0; i < n; i++) {
        result = reset(result, i);
        if (test(buffer[i / 8], i % 8)) {
            set(result, i);
        }
    }
    return result;
}

Set and Reset Functions

long long set(long long v, int i) {
    return v | (1 << i);
}

long long reset(long long v, int i) {
    return v & ~(1 << i);
}

• set() Function:

  • Takes:
    • Long long v: a 64-bit signed value.
    • Integer i: the position of the bit.
  • Returns:
    • The given values with bit i set to 1.

• reset() Function:

  • Takes:
    • Long long v: a 64-bit signed value.
    • Integer i: the position of the bit.
  • Returns:
    • The given value with bit i set to 0.

Packing

• Packing: Translates from source to destination.
• The source is an 'm'-bit integer.
• The destination is an 'n'-bit integer (n may not be 8, 16, 32, or 64 bits).
• Considerations consist of weather the integers signed(twos complement)
• The destination uses little or big endian

int pack_signed(long long src, char *buffer) {
    int n = 63; /* assume full size int */
    int sign = test(src, n);

    for (n = 63; n > 0; n--) {
        if (test(src, n - 1) != sign)
            break;
    }

    for (int i = 0; i <= n; i++) {
        buffer[i >> 3] = reset(buffer[i >> 3], i & 7);
        if (test(src, i)) {
            buffer[i >> 3] = set(buffer[i >> 3], i & 7);
        }
    }

    return n; /* Feature: Need 1 bit to encode 0 or 1 */
}

Problem: Packing an Integer

int pack_signed(long long src, char *buffer)

• Packing an Integer implementation with the following parameters:
  • src: the value to be packed, (long long) integer that could be signed
  • *buffer: pointer to the bytes containing the packing (little endian)
• Returns, the number of bits to pack the integer

Explore integer representation in computer systems, covering one's complement, two's complement, and signed vs. unsigned integers. Learn about integer ranges, addition/multiplication, and considerations for mixing signed/unsigned integers of different sizes. Understand unpacking and packing integers.