Integer Arithmetic

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.

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 2ⁿ - 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 -2^n-1, where n is the number of bits in the binary representation. For example: -5 and 5 are represented as 1011 and 0111 respectively¹.

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:

Remember this for the entirety of this post.

Due to finite nature of computer arithmetic, its results are sometimes erroneous. It's two possible causes are:

1. 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 and y 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.

2. 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 numbers².

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.

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.