Lecture 6 Integer Representation and Manipulation

Integer Representation (CSCI 1120)

• Integers can be represented using one's complement and two's complement
• Representation types include signed vs unsigned integers
• Considers representation of integer ranges and addition/multiplication

Integer Manipulation (CSCI 2122)

• The course discusses how to manipulate integers
• Systems use two's complement
• Considers mixing signed and unsigned integers
• Mixing integers of different sizes requires understanding
• Discusses how to unpack and pack integers

Lecture Outcomes

• Ability to unpack/pack integers from/to bit streams
• Ability to manipulate integer values at the bit level
• Considerations for mixing signed and unsigned integers are to be identified

Integer Types in C

• Most languages offer several kinds of integers
• Integer sizes vary based on the platform in C

Minimum Sizes

• char is at least 1 byte.
• short is at least 2 bytes.
• int is the word size of the machine.
• long is at least 4 bytes.
• long long is at least 8 bytes.

Integer Ranges on a system

• Integer types may be larger than the minimum size on some systems
• It's possible for int, long, and long long to be the same size
• Unsigned char range: 0 to 255 or 0 to (2^8 - 1)
• Signed char range: -128 to 127 or -2^7 to (2^7 - 1)
• Unsigned short range: 0 to 65536 or 0 to (2^16 - 1)
• Signed short range: -32768 to 32767 or -2^15 to (2^15 - 1)
• Unsigned int range: 0 to 4294967295 or 0 to (2^32 - 1)
• Signed int range: -2147483648 to 2147483647 or -2^31 to (2^31 - 1)
• Unsigned long range: 0 to 18446744073709551615 or 0 to (2^64 - 1)
• Signed long range: -9223372036854775808 to 9223372036854775807 or -2^63 to (2^63 - 1)

Determining Integer Size

• Applications may need to know the size of an integer

sizeof Operator

• Used to determine the size of a type
• Takes a type or a value
• Returns the number of bytes the type or value occupies
• It's used extensively when allocating memory
• char size: 1 byte
• short size: 2 bytes
• int size: 4 bytes
• long size: 8 bytes

Importance of Integer Manipulation

• Essential for programs to input and write binary data, including integers
• Important for interacting with hardware, like graphics cards
• Critical for translating binary data between different hardware and software
• Necessary when using integers as components of data structures, like bitmaps
• It's required to implement high-level numerical packages from integers at a low level

Unsigned Integers

• For an n-bit integer, the range is 0 to 2^n - 1
• Value is calculated as: bn-1 * 2^(n-1) + bn-2 * 2^(n-2) + ... + b1 * 2^1 + b0 * 2^0 where bi is the i-th bit in the int
• Addition operates bitwise with carry
• Subtraction is transformed into addition by adding the negation of y with 1 (x - y -> x + ~y + 1)

Two's Complement Examples (8-bit)

• -1 is represented: 1 = 00000001, -1 = (~1 + 1) = ~00000001 + 00000001 = 11111110 + 00000001 = 11111111 = 0xff
• -(-1) is represented: -1 = 11111111, -(-1) = (~-1 + 1) = ~11111111 + 00000001 = 00000000 + 00000001 = 00000001 = 0x01
• -0 is represented: 0 = 00000000, -0 = (~0 + 1) = ~00000000 + 00000001 = 11111111 + 00000001 = 00000000 = 0x00
• 127 + 1 is represented: 127 = 01111111 = 0x7f, 127 + 1 = 01111111 + 00000001 = 10000000 = -128 = 0x80

Usage of Two's Complement

• Signed integer representations, such as one's complement and signed-magnitude, are alternatives
• Two's complement is used because other representations have two representations for 0
• The CPU can use the same operations for both signed and unsigned integers if two's complement is used
• For two's complement all operations are the same, except expansion (copying an integer value from a smaller integral type to a larger one)
• All modern CPUs use two's complement

Problems with Signed Integers

• Tasks includes how to determine if an n-bit signed integer X (where n is not 8, 16, 32, or 64) is negative or positive
• Write a C function to determine if X < Y (without using <)

Integer Casting

• Occurs when assigning an integer between smaller/larger integral types
• When assigning a value from a larger integral type to a smaller one, the value may be truncated

Integer Truncation

• Values assigned from a larger integral type to a smaller one may be truncated
• When assigning an n-bit integral type to an m-bit integral type where n > m, the n-m most significant bits are dropped and only the m least significant bits are considered

Integer Expansion: Unsigned

• Assigned from a smaller integral type to a larger integral type, the unused bits are zeroed
• When assigning from an n-bit integral type to a m-bit integral type, where m > n, the m-n most significant bits are 0

Integer Expansion: Signed

• Assigned from a smaller integral type to a larger integral type, the unused bits are set to the sign bit (sign-extended)
• When assigning from an n-bit to an m-bit integral type, with m > n, the m-n most significant bits are set to the same value as the sign bit
• This is called sign-extension

Integer Conversion

• Assigned from a signed integral type to an unsigned integral type, the value is simply copied as is

Pitfalls of Casting

• Evaluating the bit-pattern of the int -9876 as Unsigned Binary gives: → 55660
• With an unsigned to 2sC prints ux = 4294967295, x = some value with a bit pattern

Implicit Casting

• Signed values are implicitly cast to unsigned in single expression when mixing them
• Includes comparison operators

Potential Issues With Unsigned Comparisons

• Comparison to 0U means -1 has the bit-pattern corresponding to ULONG_MAX, so the comparison is false
• Comparing 2147483647U > -2147483647 - 1 means the right-hand side is implicitly cast as unsigned, resulting in a false comparison
• However, 2147483647 > (int) 2147483647U treats the right-hand side as signed (-1), leading to a true comparison

Handling Unsigned and Negative Numbers

• When using unsigned ints it can create bugs if not handled carefully
• When mixing signed and unsigned values in comparisons, unexpected results may arise because of implicit casting (e.g., i <= length - 1)

Avoiding Issues from Signedness

• Java chose to use only signed integers to avoid these pitfalls

Downside to Signed Only

• Half the range of integers may be lost if negative numbers are not needed
• Many hardware devices use unsigned integers (e.g., hard disks and SSDs)
• More complex code may be needed to use signed integers where unsigned would be appropriate otherwise
• Most integers in systems are unsigned

Decomposing Integers

• Given a 4-byte integer, it can be decomposed into its 4 bytes in little-endian order

Application for Integer Packing

• Integer representation is optimized for speed during execution, not space
• A 64-bit integer containing the value 1 takes a lot of space

Efficient Space Allocation

• Many applications require more efficient use of space
• Include communication protocols, device interfaces, and database format
• Space-efficient and computation-efficient formats necessitates efficient conversion for use

Unpacking

• Translates a value from a space-efficient to a computation-efficient format

Packing

• Translates a value from a computation-efficient to a space-efficient format

Unpacking Process

• Process translates from source to destination
• Considers a source as an n-bit integer (n may not be 8, 16, 32, or 64 bits)
• The end point is an m-bit integer, where m > n (if possible) and it is typically 8, 16, 32, or 64

Unpacking Considerations

• Integer can be unsigned or signed (typically two’s complement)
• If the source larger or smaller than the destination
• Integer will need to be expanded if smaller
• Integer will need to be truncated if larger
• the source is little endian or big endian has to be checked
• With Little-endian unpack integer least-significant to most-significant bit
• With Big-endian unpack integer most-significant to least-significant bit

Unpacking Function

• Implementing unpacking function with Parameters includes pointer to the bytes containing value and n is the number of bits
• It returns a long long containing integer.
• The approach includes initializing result to the appropriate sign extension and copying over the bits from least significant to most significant.

SET() and RESET() Methods

• Sets a specified bit
• Takes a long long v (64 bit signed value) and integer i

Set Implementation

• Implemented with the code return v | (1

The Packing Function

• To implement the packing function Parameters needs to be passed which is integer to be packed, and bytes containing packing
• Check to see if bytes has little endian
• Then the number of bits required to pack the integer is returned

Determine the Packed Integer

• Determine size of integer by reducing sign extension to the minimum 0000000000000000000000000000000000000000000000000000000000000001
• Copy over the bits from least significant to most significant

Explore integer representation using one's complement and two's complement. Learn to manipulate integers, understanding signed vs. unsigned types and different sizes in C. Master bit-level operations and packing/unpacking.