What is an unsigned integer ?
An integer in mathematics , is any number which belong to the set Z . The set Z , contains positive whole numbers , such as : 1 , negative whole numbers such as : -1 , and the number : 0 .
Asking what is a signed or an unsigned integer , is actually asking , how to represent integers such as : -1 , 0 , and 1 , in the computer .
Representing numbers in the computer , is done on a limited number of bits , for example 8 bits , or 16 bits .
In this first part , we will describe , what is an unsigned integer , and in a second part , we will describe , what is a signed one .
Unsigned integers
This being said , we can first choose to encode the non negative numbers , as such the positive whole numbers , such as 1 or 2 etc. , and the number 0 .
Encoding in the computer can be performed using only a limited number of bits , since a computer memory is limited .
As such , once the number of bits to encode a non negative integer values has been chosen , only a limited set , of non negative integers can be represented . This limited set of non negative integers , with its encoding , is called an unsigned integer set . An unsigned integer , has a non negative numeric integer value , and it has an encoding .
Encoding in the computer , consists of representing data , using a string of bits formed only of 0 and 1 , such as 10101 , called a binary representation . Binary as in the digits used , consist only of the two values 0 , or 1 .
In unsigned encoding , non negative integers , are encoded using the binary positional numeral system . In the binary positional numeral system , 0101 as an example , has a value of 5 in the decimal positional numeral system.
In a high level programming language , unsigned integers are represented using some data type , for example in c or c++ unsigned integers , are represented using the following data types :
unsigned char
# typically 8 bits .
# at least 8 bits .unsigned short
# typically 16 bits .
# at least 16 bits .unsigned int
# typically 32 bits .
# at least 16 bits .unsigned long
# typically 64 bits
# at least 32 bits .unsigned long long
# typically 64 bits
# at least 64 bits .
Having chosen a number of bits , and how to encode non negative integers in the computer , we end up with an unsigned integer set , formed of a limited number of non negative integers and their encodings , the question to ask hence , is what operations can be performed on this set .
For all the following sections , let us say , that encoding is performed using only 2 bits , as such the unsigned integers set is :
Unsigned integer addition
Addition is performed using the binary positional numeral system , as such it works like regular addition , with carry and so on .
A problem that is faced , when performing addition using unsigned integers , is that , there is a limited number of bits used for encoding . This can lead to overflow , which is that a result is too large to be represented , using the chosen encoding .
When the result of an unsigned addition , is too large to be represented using the selected number of bits , the excessive bits are thrown away , so the resulting number of bits is truncated to fit the selected number of bits . This is the same as :
As such , the result of performing unsigned integer addition , when the numbers of bits selected for encoding , is only 2 , is :
To detect if unsigned integer addition overflow has occurred , it is sufficient to check if the result of the unsigned addition , is smaller of any of its two operands .
int unsignedAdditionOverflow( unsigned int x , unsigned int y ){
/* Check if unsigned int addition overflow ,
will occur , return 1 , if it does , 0
otherwise .*/
return ( x + y ) < x;}// end unsignedAdditionOverflowUnsigned integer multiplication
Unsigned integer multiplication , works like regular multiplication , because it is being performed using base 2 .
The problems faced by unsigned multiplication , are caused by the limited number of bits used , which lead to overflow .
For unsigned integer multiplication , when overflow occurs , the exceeding bits are thrown away , and the result is truncated to the selected number of bits . This is the same as :
As an example , a table of unsigned multiplication , when encoding is performed using two bits is :
To detect unsigned multiplication overflow in C , it can be done using this method , or one of its derivatives .
#include<limits.h>
/* The limits.h header contains the
min and max values , that integer
types in C , can have on a certain
machine . */int unsignedMultiplicationOverflow( unsigned char x , unsigned char y ){
//Check for unsigned char multiplication overflow
if( x == 0 || y == 0 )
return 0; //no unsigned char multiplication overflow
if( x == 1 || y == 1 )
return 0; // no unsigned char multiplication overflow
unsigned char z = UCHAR_MAX / x ;
/* Perform unsigned division ,
For example , x = 20 , UCHAR_MAX = 255
z = 12 .
z is the greatest number such that :
z * x <= UCHAR_MAX */
if( y > z )
return 1;//unsigned char multiplication overflow
else
return 0; /*no unsigned char multiplication overflow*/}//end unsignedMultiplicationOverflow
Unsigned integer division
Unsigned integer division works the same as regular integer division , since the division is being performed using base 2 . It returns only the quotient , without any remainder or fractional part .
No overflow can occur while performing unsigned integer division , and the result of dividing by 0 is undefined .
Unsigned integers subtraction
When subtracting , the larger unsigned value , from the smaller unsigned value , the result is correct , but when subtracting the smaller unsigned value from the larger unsigned value , the result is negative .
The formula to compute the result , when the subtraction of two unsigned integers yield a negative value , is the following :
As an example , the following tables details unsigned subtraction using 2 bits :
To check if the subtraction of two unsigned integers , will yield a modulo result , this can be done as follows :
int unsignedSubstractionModulo( unsigned char x , unsigned char y ){
// Check if y - x cause modulo result .
if( x <= y )
return 0; // no unsigned char substraction modulo result
else
return 1;/* unsigned char substraction modulo result */}// end unsignedSubstractionModuloCommutativity , associativity , and distributivity
unsigned addition
commutative : a + b = b + a
associative : a + ( b + c ) = ( a + b ) + cunsigned Multiplication
commutative : a * b = b * a
associative : a * ( b * c ) = ( a * b ) * c
distributive over addition and substraction
a * ( b + c ) = ( a * b ) + ( a * c )
a * ( b - c ) = ( a * b ) - ( a * c )unsigned Division
not commutative : ( 1 / 2 ) != ( 2 / 1 )
not associative : ( 1 / 2 ) / 3 != 1 / ( 2 / 3 )
because 0 != undefinedunsigned Subtraction
not commutative : 1 - 2 != 2 - 1
not associative : ( 1 - 2 ) - 1 != 1 - ( 2 - 1 )
Originally published at https://twiserandom.com on November 30, 2020.
