Integer Representations

Signed Integers

An ideal signed integer representation should have

• half the encoding space for negative values
• a unique encoding as a bit string for each represented integer
• a straightforward way to do arithmetic.

Signed Magnitude Representation

The most significant bit can be 0 (positive) or 1 (negative)

• E.g., 0000 and 1000 = 0, 0001 = 1 and 1001 = -1
• Downside: two represented of 0 and arthmetic is complicated
• Not used for modern computer integer representation, but is used in floating point representation.

One's Complement

To represent -x, invert all the bits of x.

• Downside: two representations of 0, slightly complicated arthmetic

Two's Complement

In w-bit word, the most significant bit represents $-2^{w-1}$.

• E.g., when w = 4, the third bit represents -8. 1010 is the same as $1(-8) + 0(4) + 1(2) + 0 = -6$
• There is asymmetry in the negative and positive range. For w = 4, -8 can be represented, but 8 cannot.
• You can also know if its negative or positive right away. The most significant bit, $w-1$ is the sign bit: if it's 0, its positive, and if its 1, then its negative.

The big advantage is that unsigned addition yields correct result for signed values!

Subtraction can be done via addition of the negated value.

To perform two's complement negation, invert all bits, then add 1.

Sign Extension

You may need to increase the number of bits in the representation of a signed integer.

• In two's complement, you can perform sign extension by replicating the original sign bit as many times as necessary while preserving the numeric value.
• Processors typically have dedicated instructions to perfrorm sign extension
• E.g., 1011 --> 11111011, 0011 --> 00000011

In general, increasing the number of bits in the representation of an integer (signed or unsigned) will preserve its value.

Side Note: to print out bits:

#include <stdio.h>
void printbits(int x, int n) {
for (int i = n - 1; i >= 0; i--) {
	putchar(x & (1 << i)) ? '1' : '0';
}
	putchar('\n')
}

• The x & (1 << i) acts like a test bit to see what is at that position.

Truncation

Truncation is reducing the number of bits in the representation of an integer.

• In general, this will lose information and potentially change the value.
• Done by chopping off bits from the left side of the bit string. Whatever remains is the new representation
  • E.g., 1110010 (-14) --> 0010 (2)

Side Note: short is a 16 bit signed type, and char is a signed 8 bit type.

Converting signed and unsigned

Fundamentally, the data in a computer's memory has no inherent meaning. It is up to the program to decide how to interpret data.

Conversions between signed and unsigned do not change the underlying representation as bits.

• E.g., 10010110 signed is -106 but 150 as unsigned.

Side Note: to parse bits

#include <stdio.h>
unsigned char parsebits(const char *s) {

  unsigned char val = 0;
  char c;
  while ((c = *s++)) {
	val <<= 1;
    if (c == '1') {
	    val |= 1;
	    }
	}

return val; }

Writing Programs

Be very careful when writing programs. The semantics of integer values and data types can be surprisingly subtle.

• C and C++ complicate matters because data type sizes vary, integer representation is not specified by the language, and some operations have semantics that are implementation-defined or undefined.

In C, implicit conversions will occur (even ones that are lossy).

• Understand where implicit conversions happen to understand their effect.
• Use explicit type casts so that conversions are explicit even if they aren't necessary. It makes the semantics of the program more obvious.
• E.g., You pass an unsigned integer into a function that is expecting a signed integer.

Sign extension can have surprising consequences:

• Bits that you thoguht would be 0 become 1
• Values belonging to unsigned types (unsigned char, unsigned short, etc.) are never sign extended.