Integer Arithmetic
2022-06-12
Introduction
In this blog post we will try to analyse Integer Arithmetic from the perspective of an programmer. Additional, we are going to see the facilities provided by the underlying instruction set for its error detection.
Representation
There are two different ways of integer representation, one that can only represent positive numbers and another can represent negative, zero and positive numbers.
The former is called unsigned representation, which can represent
values from 0 to 2n - 1, where n
is the number of bits in the
binary representation. For example: 12 and 15 are represented as
1100
and 1111
respectively.
The later is called signed representation. There are multiple
encoding for signed representation, most common being Two's Complement
representation. It is defined by interpreting the most significant bit
as sign bit, having a negative weight of -2n-1, where n
is the
number of bits in the binary representation. For example: -5 and 5
are represented as 1011
and 0111
respectively1.
Hexadecimals
Hexadecimals numbers (or Hex) are base-16 numbers which uses digits through 0 to 9 and characters A to F to represent 16 possible values. Additionally, 4 binary numbers makes up 1 hex, here's the conversion chart:
Binary | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111 |
Hex | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F |
Remember this for the entirety of this post.
Arithmetic Errors
Due to finite nature of computer arithmetic, its results are sometimes erroneous. It's two possible causes are:
Invalid Carry. It happens when either addition or subtraction of two numbers cause carry into or borrow from the most significant bit respectively. For example, an invalid carry looks like:
uint8_t x = 0xff, y = 1; printf ("0x%hhx\n", x + y); /* Prints 0x0 */
Here we are declaring two 8-bit variables
x
andy
with values Oxff (or 255) and 1 respectively. Now, on adding them we get 256, which requires at least 9-bit for its representation, but since we are using 8-bit representation we are left with 0.Overflow. It happens when addition of two numbers with sign bits ON and OFF results a numbers with sign bit OFF and ON respectively. For example, consider the addition of these negative numbers:
int8_t x = -128, y = -1; printf ("0x%hhx\n", x + y); /* Prints 0x7f */
Again, we have two 8-bit variables. On addition, we get 0x7f (or 127), which surprisingly is an positive value because -129 requires at least 9 bits in Two's complement representation which looks like:
1 0111 1111
.
Additionally, Invalid Carry leads to erroneous arithmetic of unsigned numbers whereas Overflow only affects signed numbers2.
Detecting Errors
Based on the above definitions of the errors, its possible to detect invalid arithmetic in C. But, in my experience, its much more effective to fallback to the capabilities of the underlying assembly language for "these" kinds of problem. Here, we will use Carry Flag and Overflow Flag, which as the name suggest, will be used to detect Invalid Carry and Overflow respectively.
For example, consider the function prototype below:
int is_uadd_valid (unsigned long, unsigned long);
Function is_uadd_valid
return 1 if unsigned addition of its
arguments is valid, and 0 otherwise. It's definition in x86 assembly
language looks like:
.globl is_uadd_valid is_uadd_valid: addq %rsi, %rdi setnc %al movzbl %al, %eax ret
Here, function arguments are stored in register %rsi
and %rdi
.
Then instruction addq
, adds the values stored in these registers,
and saves it to register %rdi
. Next, we check the carry flag, and
set register %al
if it's NOT set. At last, we move this value to
register %eax
, the return value of our function.
Similarly, for signed addition in Two's complement form, we can use:
.globl is_tadd_valid # int is_tadd_valid (long, long) is_uadd_valid: addq %rsi, %rdi setno %al # Changed movzbl %al, %eax ret
Since this is signed arithmetic, we are going to check Overflow flag,
and set register %al
if it's NOT set.
Conclusion
The world of computer arithmetic is bit more nuanced than presented in this post, but I hope you found this useful. Next, read Computer Systems: A Programmer's Perspective, a introductory book for computer architecture for an detailed analysis of Interger Arithmetic and further advanced topics.
Footnotes:
See Wikipedia's entry on Two's Complement representation.
Prof. Ian D. Allen notes on Carry flag and Overflow flag.