Integer Representations

1Learning Outcomes¶

• Understand tradeoffs between integer representations:

  • (unsigned) integers

  • (signed) Sign-Magnitude

  • (signed) Ones’ Complement

  • (signed) Two’s Complement

  • Bias Encoding

• Translate between decimal numbers and other integer representations

• Identify when and why integer overflow occurs

• Perform simple binary operations like addition

2Introduction¶

Historically, computers were used as scientific calculators. We therefore dedicate most of our time to understanding how a string of bits (a bit string) can represent a number.

How can we use $N$ bits to represent a set of integers?

There are many systems we can use. Not all systems will help us represent $2^N$ unique integers in $N$ bits! We will focus on representing signed and unsigned integers.

• Signed integers refer to positive integers, negative integers, and zero.

• Unsigned integers refer to non-negative integers, i.e., zero or greater.

3$N$-bit Unsigned Integer Representation¶

Let’s get our standard unsigned integer representation out of the way first. The mathematical scheme discussed earlier is sufficient for representing $2^N$ unsigned integers with $N$ bits.

• 0b0...0 ($N$ zeros) represents zero

• 0b1...1 ($N$ ones) represents $2^N - 1$ (why?)

• Everything else: Assume the bitstring is the base-2 representation of a number. Convert.

This representation is supported in C (discussed more later). Built-in types like unsigned int can introduce ambiguity because it doesn’t specify the width of an int. The header inttypes.h accommodates typedefs like uint8_t, uint16_t, uint32_t, etc. to specify unsigned integer representations that are 8-bit, 16-bit, 32-bit etc.

4Design Considerations¶

We will prefer certain systems over others, depending on what sorts of integer operations we want to support.

4.1Common number operations¶

In decimal, we like to add, subtract, multiply, divide, and compare numbers. So we must be able to do the same thing with bit representations of numbers.

It turns out that many arithmetic operations translate reasonably well between decimal and binary.

For example, let’s add 10 and 7, which are 1010 and 0111, respectively, in binary. The result is the number 17, or 10001 in binary.

Subtraction in binary works similarly. We leave an in-depth discussion of implementing binary comparison (e.g., $X < Y$) to a future project.

4.2The Odometer Analogy¶

In theory, numbers have an infinite number of digits (usually leading zeros), but in computing, we must allocate a finite number of bits. Hardware is limited! Binary bit patterns are therefore abstractions: they are simply representatives of numbers.

In choosing an integer representation, we must consider whether the operations supported will still work within the given bit width of an integer representation. One useful analogy for considering edge cases comes from the idea of an odometer:

Two sets of values to consider:

• The binary values 000...000, 000...001, 000...010, ..., 111...111

• Integers incrementing by one, as placed on a number line

As we will see, there are systems in which the “directions” of these values may diverge.

4.3Integer Overflow¶

Integer overflow: The arithmetic result is outside the representable range of integers.

Suppose we use $N$ bits to represent integers in hardware. If the result of an integer operation ($+, -, \times, \div, <, =, \leq$, etc.) cannot be accurately represented in $N$ bits, we say that integer overflow occurred.

4-bit unsigned integers: Using 4 bits, you can represent 0 through 15.

• Positive Overflow: If you are at 15 (0b1111) and add 1, the value wraps around to 0 (0b0000).

• Negative Overflow: If you are at 0 (0b0000) and subtract 1, it wraps around to 15 (0b1111).

4.4$N$-bit Signed Integer Representations¶

How do you represent negative numbers? More generally, how do you represent both positive and negative numbers (and zero) with the same $N$ bits?

Sidebar: There was a king who asked his wise thinkers to teach him economics. They kept bringing him long books, and he kept sending them away to make it shorter. Finally, they came back and said, "Sire, we have the theory of economics in four words: ‘Ain’t No Free Lunch.’ " It means you can’t get something for nothing.

If we want to represent negative numbers, you’ve got to give something up; you lose some of the positive numbers you used to have. If we borrow a bit, we can’t go as high in the positive range, but now we can do negatives.

Next, we discuss a few reasonable ones and consider tradeoffs. In the next section, we’ll reveal the standard representation used in modern architectures and supported by the C23 standard.

5Sign-Magnitude¶

• Leftmost sign bit: the integer’s sign. 0 is positive; 1 is negative.

• Rest of bits: magnitude of the integer in binary

We already see one problem! With a positive and a negative zero, we’d have to check for two different patterns in code, every time we want to compare values to zero.

Let’s examine a subtler problem, revealed via the binary odometer:

The problem with Sign and Magnitude is that as the odometer goes up, it goes the wrong way: you go positive, positive, and then suddenly you hit the negative range. Incrementing the binary odometer 0000 to 1111 starts at 0, then 1, through to 7, then wraps to 0 again, then -1, then -7. In other words, sometimes integer addition corresponds to adding bits, and sometimes integer addition corresponds to subtracting bits. This would get complicated very quickly!

Ultimately, Sign-Magnitude is considered a straw man^[1] approach for supporting general purpose computing with integers. Nevertheless, it has some reasonable applications in, say, signals processing, where users are more commonly looking to decouple sign from magnitude, much less add numbers together. Ask us for more.

6Ones’ Complement¶

To represent a negative number, complement the bits of its positive representation.

Here, “complement” means that if the bit is 0 change it to 1, and vice versa. Equivalently, to change the sign of a number, flip all bits of its binary representation.

-7 with 8-bit Ones’ Complement

Further Explanation

Consider adding $5+(-5)$ with 4-bit one’s complement integers.

• +5: 0101

• -5: 1010

Addition: 0101 + 1010 = 1111, or -0. Arithmetic addition can be implemented with binary addition, regardless of operand sign.

...But we still have the problem of two zeros! Historically, one’s complement was used for a while, but eventually abandoned for two’s complement.

7Two’s Complement¶

Ones’ complement:

• Problem: Negative mappings “overlap” with the positive ones, creating the two 0s.

• The solution: Shift the negative mappings left by one.

Of note:

• Like in ones’ complement, incrementing the binary odometer corresponds with integer addition by one.

• 0b0000 is still 0.

• Positive numbers are the same as ones’ complement.

• Negative numbers are shifted over! For example, 0b1111 now maps to -1. This gives us one extra negative number.

• The most significant bit (leftmost bit) can still be interpreted as the sign bit.

In Two’s Complement, a bit pattern of all ones is -1.

7.1Arithmetic and conversion¶

Hardware for two’s complement is now simple.

Addition is exactly the same as with an unsigned number.

The numbers 5 and -5 are represented in 4-bit two’s complement with 0b0101 and 0b1011, respectively. Adding them together should result in 0, or 0b0000.

7.2Formal definition¶

We can write the value of an $n$-digit two’s complement number as

Positive and negative numbers can be computed using the same formula. Above, the sign is computed by multiplying the highest bit by $(-2^{n-1})$.

7.3Two’s Complement: Flip sign¶

Hardware to convert positive to negative (& vice versa) is simple.

1. Complement all bits

2. Then add 1

At home: Prove algorithm is equivalent to formula!

The intuition comes from a “number wheel” representation of our binary odometer (Figure Figure 9). This wheel also helps us identify where integer overflow occurs:

In Figure 9, 0 through 7 stays the same as it has for every representation. But then it jumps to -8. That cool top-level term (-8) pulls all negative numbers down by one so there is no overlap at zero.

7.4Two’s Complement: C standard (as of 2025)¶

Two’s complement is the C23 standard number representation for signed integers. Again, the built-in int is ambiguous because it does not specify bitwidth. And again, the header stdint.h accommodates typedefs like int8_t, int16_t, int32_t, etc., for signed integer representations.

8Bias Encoding¶

Bias Encoding:

• Keep track of a bias.

• To interpret stored binary: Read the data as an unsigned integer, then subtract the bias

• To store an integer as data: Add the bias, then store the resulting number as an unsigned integer.

Imagine you are recording an electrical signal wavering between 0 and 31 volts. Wouldn’t it be cool to grab that graph and pull it down so it wiggles around zero? That’s bias encoding.

We can shift to any arbitrary bias we want to suit our needs. To represent (nearly) as many negative numbers as positive, a commonly-used bias for $N$-bits is $(2^{N-1} - 1)$.

Here are some diagrams in case they are useful. Figure 11 represents a bias encoding where $N = 4$ and bias $= 7$. The odometer just does the right thing; it counts up through zero with nothing strange happening.

You may also find the number wheel useful for seeing where overflow happens, and how integers increase with respect to binary incrementing. See Figure 12.

We really like biased encoding for some specific applications we’ll see later in the course.