Understanding how computers handle integers is foundational to computer science and software development. In this post, we’ll explore how integers are stored, represented, and manipulated in binary systems.

What Are Integer Data Types?

Integers are whole numbers (no fractions) that can be positive, negative, or zero. In programming, they’re categorized into two types:

  1. Unsigned Integers: Non-negative values (0, 1, 2, …)
  2. Signed Integers: Positive, negative, and zero

These values are stored as binary sequences (0s and 1s), where longer bit sequences allow larger numbers to be represented.

Binary Representation Basics

Computers use the base-2 system, where each bit represents a power of 2. The rightmost bit is the least significant bit (LSB), and the leftmost is the most significant bit (MSB).
Example:
1000 in binary equals: 1×2³ + 0×2² + 0×2¹ + 0×2⁰ = 8

Binary representation of integers Binary representation of integers

Unsigned Integers

An unsigned integer uses all the bits in a binary string to represent positive numbers. For example, with a 4-bit binary sequence, we can represent the following range of numbers:

  • Minimum (binary): 0000 = Decimal: 0

  • Maximum (binary): 1111 = Decimal: 15

Signed Integers

Signed integers need to represent both positive and negative numbers. A common method to achieve this is by reserving one bit (usually the most significant bit, or MSB, the leftmost bit) as the sign bit. The value of this bit indicates whether the number is positive or negative:

  • 0 indicates a positive number.

  • 1 indicates a negative number.

Methods for Representing Signed Integers

Since signed integers need to handle both positive and negative numbers, various encoding methods have been developed over time. Here are three of the most important ones:

  1. Sign-Magnitude Representation (also known as Sign-Bit Representation):
    This is one of the simplest and oldest methods, used by early computers like the IBM 7090. It works similarly to the mathematical representation of numbers, where a sign (e.g., + or -) is placed before the value. The MSB acts as the sign bit, with 0 for positive and 1 for negative. For example:
BinaryDecimal
0000+0
0001+1
0010+2
0011+3
0100+4
0101+5
0110+6
0111+7
1000-0
1001-1
1010-2
1011-3
1100-4
1101-5
1110-6
1111-7

However, this method had several problems:

  • Two representations for zero: +0 (0000) and -0 (1000).
  • Arithmetic operations like addition and subtraction required different logic for positive and negative numbers, leading to complexity in hardware and software:
BinaryDecimalBinaryDecimalBinaryDecimal
Number-10010+20111+71101-5
Number-21010-21010-20011+3
Binary addition1100-40001+10000+0
Decimal addition+0+5-2
  • Signed extension doesn’t work for negative numbers:
Integer4-bit5-bit6-bit
+2001000010000010
+7011100111000111
-2101010010 (! = 11010)100010 (! = 111010)
-7111110111 (! = 11111)100111 (! = 111111)
  1. One’s Complement:
    This method also uses the MSB for the sign, But to represent a negative number, we take the bitwise complement (NOT operation) of the corresponding positive number by flipping all bits. For example:
Binary RepresentationDecimal Value
1’s complementSigned bit
0000+0+0
0001+1+1
0010+2+2
0011+3+3
0100+4+4
0101+5+5
0110+6+6
0111+7+7
1000-7-0
1001-6-1
1010-5-2
1011-4-3
1100-3-4
1101-2-5
1110-1-6
1111-0-7
While this simplified some operations, it still had the problem of two zeros (+0 and -0).
  1. Two’s Complement:
    This is the most commonly used method today. It’s similar to one’s complement but with an additional step: after computing the complement, add 1 to the result. For example:
Binary RepresentationDecimal Value
2’s complement1’s complementSigned bit
0000+0+0+0
0001+1+1+1
0010+2+2+2
0011+3+3+3
0100+4+4+4
0101+5+5+5
0110+6+6+6
0111+7+7+7
1000-8-7-0
1001-7= inverse of 7 + 1-bit-6-1
1010-6= inverse of 6 + 1-bit-5-2
1011-5= inverse of 5 + 1-bit-4-3
1100-4= inverse of 4 + 1-bit-3-4
1101-3= inverse of 3 + 1-bit-2-5
1110-2= inverse of 2 + 1-bit-1-6
1111-1= inverse of 1 + 1-bit-0-7

Two’s complement solves the zero problem and simplifies arithmetic operations, making it the standard in modern computing.

Overflow in Integer Arithmetic

When an arithmetic operation’s result exceeds a binary string’s range, an overflow occurs. For example, in an 8-bit binary system, adding 1 to the largest number (255) will cause an overflow, and the result will wraparound to 0.

A real-world analogy is mechanical counters, like odometers. When they reach their maximum value (e.g., 99999), adding one causes them to roll over to 00000.

Odometer Rollover

Odometer Rollover

Overflow can occur in subtraction as well. In two’s complement, subtracting 1 from the smallest number (e.g., -128 in an 8-bit system) will result in +127 due to overflow. Hardware usually detects and signals overflow through condition codes. In two’s complement, a simple rule to detect overflow is:
If the carry in to the sign bit differs from the carry out of the sign bit, an overflow has occurred.

BinaryDecimalBinaryDecimalBinaryDecimalBinaryDecimal
Number-11011-5001020111+71011-5
Number-21100-4011061110-200113
Addition(1) 0111(0)1000(1)0101(0)1110
carry in to sign bit0overflow1overflow1no0no
carry out to sign bit1010

Integer Representation in Programming Languages

  1. C/C++:

    In C, there are various integer types to specify size, such as int, short, long, and long long. The exact size depends on the system architecture. Signed and unsigned integers are explicitly defined with signed or unsigned.

  2. Go:

    Go offers specific integer types for each size, such as int8, int16, int32, and int64 for signed integers, and uint8, uint16, uint32, and uint64 for unsigned integers.

  3. Java:

    Java is more limited, providing only int (32-bit) and long (64-bit). Both are signed by default, and Java doesn’t support unsigned integers.

Conclusion

Understanding how integers are represented and processed in computers is crucial for tasks like optimizing application performance, designing robust algorithms, and avoiding common issues like overflow. By mastering this topic, you can write more efficient and reliable programs.

For those interested in exploring these topics further, I highly recommend the book Computer Systems: A Programmer’s Perspective. It provides an in-depth and fascinating look at how computers work under the hood.