06. Integers

Integers#

A computer does not store the abstract idea of the number 42. It stores a finite pattern of bits, and the type of the value tells us how that pattern should be interpreted. The same 32 bits could represent a signed integer, an unsigned integer, a floating-point number, a Unicode code point or even a MIPS instruction. Without context, a bit pattern is only a bit pattern.

This note develops the representation of integers from the ground up. The ideas here are what allow us to make sense of the values shown by mipsy, understand why overflow occurs and predict what the byte-loading instructions in Using MIPS will do. It follows the assessable conventions in the official COMP1521 integer notes, with additional explanation around the places where the representation tends to become confusing.

Positional Number Systems#

The decimal number 4705 is shorthand for:

$$4\times10^3 + 7\times10^2 + 0\times10^1 + 5\times10^0.$$

Decimal is a base 10, or radix 10, number system. There are ten possible digits, 0 through 9, and the position of a digit determines the power of ten by which it is multiplied. There is nothing fundamentally special about ten; it is simply the base humans commonly use.

In a base $b$ system, a number with digits $d_nd_{n-1}\ldots d_1d_0$ has the value:

$$\sum_{i=0}^{n} d_i b^i.$$

Every digit must be between $0$ and $b-1$. For example, 1216 is valid in base 7 because all of its digits are less than 7:

$$(1216)_7 = 1\times7^3 + 2\times7^2 + 1\times7^1 + 6\times7^0 = (454)_{10}.$$

Binary#

Computers commonly represent values using binary, or base 2. Binary has only two digits, 0 and 1; each binary digit is therefore called a bit. The place values are powers of two:

Consequently:

$$(1011)_2 = 1\times8 + 0\times4 + 1\times2 + 1\times1 = (11)_{10}.$$

The bit on the far right has the smallest place value and is called the least significant bit (LSB). The bit on the far left has the largest place value and is called the most significant bit (MSB).

Converting binary to decimal#

To convert from binary to decimal, add the place values corresponding to the 1 bits. For example:

$$(11001)_2 = 16 + 8 + 1 = (25)_{10}.$$

Converting decimal to binary#

One method is to repeatedly divide by two and record each remainder:

Reading the remainders from bottom to top gives $(11001)_2$.

Another method is to subtract powers of two. The largest power of two no greater than 25 is 16, leaving 9. We can then use 8, leaving 1, before finally using 1. The selected place values are therefore 11001.

Hexadecimal#

Binary values become long very quickly. Hexadecimal, or base 16, gives us a compact notation which still exposes the underlying bits. Its digits are:

Since $16=2^4$, exactly four bits correspond to one hexadecimal digit. To convert between binary and hexadecimal, group the bits into groups of four starting from the radix point:

1011 1100 0110 0001 0100 1110
   B    C    6    1    4    E

Thus $(101111000110000101001110)_2=(\text{BC614E})_{16}$.

Hexadecimal place values are powers of 16. For example:

$$(3\text{AF1})_{16}=3\times16^3+10\times16^2+15\times16+1=(15089)_{10}.$$

Octal#

Octal, or base 8, uses the digits 0 through 7. Since $8=2^3$, one octal digit represents exactly three bits. Octal is less common for general bit patterns than hexadecimal, but we will see it again when writing Unix file permissions.

111 010 = 72 in octal = 58 in decimal

The important grouping rule is therefore:

Integer Constants in C and MIPS#

C and mipsy accept several notations for an integer constant:

int a = 42;          // decimal
int b = 0x2A;        // hexadecimal
int c = 052;         // octal
int d = 0b101010;    // binary in the COMP1521 toolchain

All four variables contain the same value. The prefix changes how the source text is parsed; it does not permanently attach a base to the value in memory. Binary integer constants were only standardised recently and are not accepted by every older C compiler, although the COMP1521 toolchain accepts the form shown here.

The printf format specifier determines the notation used when displaying the value:

printf("%d\n", a);  // 42
printf("%x\n", a);  // 2a
printf("%o\n", a);  // 52

Bits, Bytes and Integer Types#

A byte is the smallest independently addressable unit of memory. On the systems used in COMP1521, one byte contains eight bits. Common C type sizes on CSE are:

These sizes are common, but C does not require every machine to use them. sizeof(type) reports the size on the current system, whilst <limits.h> provides constants such as INT_MIN, INT_MAX and UINT_MAX.

When the precise width matters, <stdint.h> provides fixed-width types:

#include <stdint.h>

int8_t signed_byte;
uint8_t unsigned_byte;
int16_t signed_halfword;
uint32_t unsigned_word;
int64_t signed_doubleword;

We use these types frequently in COMP1521 because uint32_t tells the reader considerably more than “some unsigned integer”. The GNU C Library's integer type documentation gives a broader overview of the exact-width types.

Why getchar returns an int#

getchar must represent every possible byte value and the special negative value EOF. A char may not have enough distinct values for both:

int c;
while ((c = getchar()) != EOF) {
    putchar(c);
}

If c were a signed 8-bit char, the byte 0xFF could become -1 and be mistaken for EOF. If plain char were unsigned, the real EOF value could instead be converted into a non-negative byte and never compare equal. The wider int return type avoids both problems.

Unsigned Integers#

An $n$-bit unsigned integer assigns every bit a non-negative place value. Its range is:

$$0\text{ to }2^n-1.$$

An unsigned 8-bit integer therefore ranges from 0 to 255:

00000000 =   0
00000001 =   1
11111111 = 255

For a 32-bit unsigned int, the range on CSE is 0 to $2^{32}-1$, or 4,294,967,295.

Unsigned wrap-around#

There are only $2^n$ possible patterns in an $n$-bit unsigned type. Arithmetic performed in that unsigned type is defined modulo $2^n$, so a result outside the range wraps around.

uint8_t x = 255;
x = x + 1;           // 0

uint8_t y = 0;
y = y - 1;           // 255

There is one extra C detail in these uint8_t examples. Types narrower than int undergo integer promotion, so x + 1 and y - 1 are calculated as int on the CSE machines. The value then wraps when it is converted back to uint8_t by the assignment. With a 32-bit unsigned int, the arithmetic itself is already unsigned and wraps modulo $2^{32}$.

This is not the computer “forgetting” to check for overflow. The modulo conversion and unsigned-arithmetic rules are specified by C and are useful when wrap-around is intentional. They are dangerous when an attacker can make a size calculation wrap into a much smaller value.

Signed Integers and Two's Complement#

Signed integers need to represent both positive and negative values. Modern systems use two's complement representation.

For a signed $n$-bit value, the most significant bit has place value $-2^{n-1}$, whilst the remaining bits retain their ordinary positive place values:

$$-b_{n-1}2^{n-1}+\sum_{i=0}^{n-2}b_i2^i.$$

This gives the range:

$$-2^{n-1}\text{ to }2^{n-1}-1.$$

For eight bits:

01111111 =  127
00000001 =    1
00000000 =    0
11111111 =   -1
11111110 =   -2
10000000 = -128

There is one more negative value than positive value. In particular, -128 has no positive int8_t counterpart.

Interpreting a negative bit pattern#

If the leading bit of an $n$-bit pattern is 1, interpret it as an unsigned number and subtract $2^n$:

$$(11000011)_2=195\text{ unsigned}=195-256=-61\text{ signed}.$$

Alternatively, invert the bits and add one to obtain the magnitude:

11111011    representation of -5
00000100    invert every bit
00000101    add one -> magnitude 5

The same procedure transforms +5 into -5, because negation in two's complement is ~x + 1.

Why two's complement is useful#

Two's complement has only one representation of zero, and the same binary adder can handle both signed and unsigned addition. Consider 5 + (-2) using eight bits:

  00000101
+ 11111110
----------
1 00000011

The ninth carry bit does not fit and is discarded, leaving 00000011, or 3. The hardware performed ordinary binary addition; the interpretation of the operands made it signed arithmetic.

Signed overflow#

The mathematical result of signed arithmetic may fall outside the representable range. In C, signed integer overflow is undefined behaviour. A compiler is permitted to assume it never occurs and optimise accordingly. This is importantly different from the defined modulo behaviour of unsigned arithmetic.

int x = INT_MAX;
int y = x + 1;       // undefined behaviour

On a typical two's-complement processor the bits may appear to wrap to INT_MIN, but portable C must not rely upon that outcome. Before performing a potentially overflowing signed calculation, either prove that the result is in range, check the operands, or use an appropriate wider/unsigned representation.

The Same Bits, Different Meanings#

The pattern 11111111 illustrates why type information matters:

A cast may change only the interpretation of existing bits, or it may also change the width and therefore require extension or truncation. You should always ask two questions:

1. How many bits are present?
2. Are those bits being interpreted as signed or unsigned?

Extending and Truncating Values#

MIPS general-purpose registers are 32 bits wide, but memory can hold byte and halfword values. Loading a smaller value therefore requires deciding what fills the unused upper bits.

Zero extension#

An unsigned value is zero-extended: zeroes are placed in all new upper positions.

8-bit value:      10000000       = 128 unsigned
32-bit result:    00000000 00000000 00000000 10000000

The MIPS instructions lbu and lhu load an unsigned byte or halfword and zero-extend it to 32 bits.

Sign extension#

A signed value is sign-extended: the original sign bit is copied into every new upper position.

8-bit value:      10000000       = -128 signed
32-bit result:    11111111 11111111 11111111 10000000

The MIPS instructions lb and lh treat the loaded value as signed and sign-extend it. Copying the sign bit preserves the value because each new leading 1 contributes the negative place value needed to balance the new positive place values.

Truncation#

Converting to a narrower type discards the high-order bits that do not fit:

32-bit value:  0x1234ABCD
low 16 bits:       0xABCD
low 8 bits:          0xCD

Truncation can change a value dramatically. It is safe only when the programmer knows that the discarded bits are unnecessary or deliberately wants a modulo-$2^n$ result.

Endianness#

Multi-byte values occupy several consecutive byte addresses. Endianness determines which byte is stored at the lowest address.

Suppose the 32-bit word 0x12345678 begins at address 0x1000:

• Big-endian stores the most significant byte at the lowest address.
• Little-endian stores the least significant byte at the lowest address.

Mipsy-web uses little-endian memory. Consequently, this code loads 0x78 into $t1:

.text
main:
    li  $t0, 0x12345678
    sw  $t0, my_word
    lbu $t1, my_word

.data
my_word:
    .space 4

Endianness changes the order of bytes in memory, not the order of bits within a byte and not the written order of hexadecimal digits in a register. If mipsy shows $t0 = 0x12345678, the register still contains that numeric value regardless of how a later sw arranges its bytes.

flowchart TB
    W["Word: 0x12345678"] --> BE["Big-endian<br/>low to high: 12 34 56 78"]
    W --> LE["Little-endian<br/>low to high: 78 56 34 12"]

Integers as MIPS Instructions#

Every classic MIPS instruction is itself a 32-bit value stored in the text segment. The processor does not see the textual instruction add $s1, $t1, $t0; the assembler encodes its operation and operands into fields.

0x01288820
= 000000 01001 01000 10001 00000 100000
  opcode   rs    rt    rd   shamt funct

For this R-type instruction:

• opcode = 000000 selects the R-type group;
• rs = 01001 is register 9, $t1;
• rt = 01000 is register 8, $t0;
• rd = 10001 is register 17, $s1;
• shamt = 00000 is the unused shift amount here;
• funct = 100000 selects signed add.

The resulting instruction is:

add $s1, $t1, $t0

This is another example of the same principle: the bits acquire meaning only when we know the format through which they are being interpreted.

Common Mistakes#

• Treating a bit pattern as inherently signed or unsigned. Signedness belongs to the interpretation.
• Forgetting the width. 0xFF is -1 as an int8_t, but 255 as a uint32_t.
• Assuming signed overflow safely wraps. In C, it is undefined behaviour.
• Believing endianness reverses all the bits. It reorders bytes, not bits within each byte.
• Using lb when the source byte is unsigned. Values from 0x80 to 0xFF will be sign-extended into negative 32-bit values.
• Reading 010 as decimal ten in C. It is an octal constant with the value eight.
• Negating INT_MIN. Its positive magnitude cannot be represented in the same signed type.

Practice#

1. Convert $(10110110)_2$ to hexadecimal and decimal.
2. Write -42 as an 8-bit two's-complement pattern.
3. Interpret 0xA7 as both uint8_t and int8_t.
4. A little-endian machine stores 0xCAFEBABE beginning at address 0x2000. Which byte appears at addresses 0x2000 through 0x2003?
5. What values do lb and lbu produce when loading the byte 0x80?

The next step is to stop treating these bits merely as numbers and begin deliberately manipulating individual positions using Bitwise Operations.