What is a signed integer ?
The question , what is a signed integer , is the question how to represent integers in the computers .
In mathematics , integers belong to the set Z , which contains positive and negative whole numbers such as -1 or 1 , and the number 0 .
As shown in an earlier article , non negative numbers can be represented by using the unsigned method , but we still need a way to represent negative integers such as -1 and -8 , hence the signed representation .
In the signed representation , first the number of bits to perform the encoding is chosen . A bit can have only one of the two values : 0 or 1 . This is called a binary representation . Binary as in 0 or 1 .
What remains is to determine , how the mapping from the integers to the binary encoding , and from the binary encoding to the integers will be performed . This is called the algorithm .
There exist multiple algorithms to perform such a task , the most well known are : the two’s complement representation , the one’s complement representation , and the sign and magnitude representation .
Two’s complement representation
In two’s complement representation , the algorithm divides the selected number of bits in two parts , one represents a negative value , and one represents a positive value .
The first bit to the left , is considered to have a negative value , equal to :
So if the number of bits is 4 , then the negative part has a min value of -8 , and a max value of 0 .
The remaining bits are considered to be in the binary positional numeral system , and they represent a positive value . So if the number of bits is 4 , then the last 3 remaining bits , are considered to be in the binary positional numeral system , hence they have a max value of 7 , and a min value of 0 .
The final value of the bit representation , is the sum of the negative part , and of the positive part . So if the number of bits is 4 , then we have these possible values .
A two’s complement number as such , has a integer value , it can be positive , negative or 0 , and it has , as described earlier , an encoding . In the encoding , the first bit to the left , is considered to have a negative value , and the remaining bits , are considered to be in the binary positional numeral system , as such they have a positive value . The integer value of a two’s complement number , is the sum of the values , of its negative and positive parts .
The set of all two’s complement numbers , encoded with a specific number of bits , is called a two’s complement set , and is formed of integer values , and their encodings , as shown in the previous table .
This being said , the question now to ask , is what are the properties of the operations that can be performed on a two’s complement set .
Converting an integer to its two complement representation and vice versa
The question how to convert an integer to its two’s complement form , is just asking how to represent it in binary , binary as in 0 and 1 , as , a two's complement number integer value , is the same one as an integer belonging to the set Z .
If the number is positive , then the number can be converted to two’s complement binary form , by first representing it using the binary numerical positional system . For example :
And later on concatenating one 0 valued bit , to its left , to represent the sign bit . So in our example , 6 can be represented in two's complement binary form , as 0110 .
To represent a negative value ng , first get p , where p is equal to 1 plus , the power of two , larger or equal to the absolute value of ng . Next calculate the value mod , which is equal to 2 to the power of p . Add ng to mod , to obtain the value comp .
Represent this value in the binary positional numeral system . This representation is the two’s complement , binary representation of ng . An example to illustrate this :
To convert from two’s complement binary form , to an integer value , it can be done as shown in the Two’s complement representation section , which is multiply each bit by 2 to the power i , where i is equal to 0,1,2.. Subtract the converted value of the first bit to the left , from the sum of the converted values of the rest of the bits , to get the integer value. As an example :
Two’s complement addition
Adding two , two’s complement numbers when performed on their integer value , can be done as a regular base 10 addition . Since a two's complement number is represented using only a limited number of bits , this means that performing two's complement addition , will lead to overflow .
When overflow occurs , and when the resulting number is negative , take its positive modulo . If the resulting number is positive , take its negative modulo . The modulo is calculated with regards to two to the power of the number of bits , used to represent the two’s complement number .
To perform the addition of two , two’s complement numbers , on the bit level , just do the addition in base 2 , and truncate any overflow , and you will get the correct result .
To detect, if an overflow will occur while performing addition in two’s complement , it can be done like this :
int overflowSignedAddition( signed char x , signed char y ){
// Check if x + y will cause an overflow signed char additionsigned char x_plus_y = x + y ;if( x >= 0 && y >=0 )
return x > x_plus_y;
/* If both operand positive , and any of
the operands larger than the result ,
this means we have a signed addition
overflow . */
else if ( x < 0 && y < 0 )
return x < x_plus_y ;
/* If both operand negative , and any of
the operands smaller than the result ,
this means we have a signed addition
overflow . */
else
return 0; /*no overflow signed addition*/}//end overflowSignedAddition
Two’s complement subtraction
Subtracting two , two’s complement number , can be performed using their integer values , this can lead to overflow , when the result of the subtraction is outside the range of possible integer values , determined by the number of bits selected to form the two’s complement set .
Hence , the question to ask is , if such overflow occurs , how to represent it in the selected two’s complement set .
It was chosen that if the overflow is on the negative side of the range , represent it using its positive modulo , and if the overflow is on the positive side of the range , represent it using its negative modulo .
The modulo is computed with regards , to two to the power of the number of bits , chosen to form the two’s complement set .
To subtract two two’s complement numbers using their bit representation , perform subtraction as in base 2 , and truncate the result to fit the selected number of bits . Interpret the result , as being in two's complement binary form .
To detect if a two’s complement subtraction will cause an overflow , it can be done with something like this .
int overflowSignedSubtraction( signed char x , signed char y ){
/*
check if a two's complement signed int
overflow will occur , when performing
the operation x - y */signed char x_minus_y = x - y ;if( x >= 0 && y < 0 )
return x_minus_y < 0 ;
/* if x >= 0 , and y < 0
, x - y must be > 0 , if
it is less than 0 , this
means that a signed subtraction
overflow has occured .*/
else if( x < 0 && y >= 0 )
return x_minus_y > 0 ;
/*
if x < 0 , and y >=0 ,
, x - y must be < 0 ,
if it is larger than 0 ,
then this means that a signed
subtraction overflow has
occured .*/
else
return 0;
/* else , no signed subtraction
overflow has occured*/;} // end overflowSignedSubtraction
Two’s complement multiplication
To perform the multiplication of two , two’s complement numbers , perform the multiplication on their integer value , just like you perform a regular multiplication .
Overflow can arise , when performing multiplication between two , two’s complement numbers , because two’s complement numbers are represented using a limited number of bits . The limited number of bits , yield a limited possible number of two’s complement integer values .
When overflow occurs , substitute the overflown result with its modulo representation . The modulo representation , must fit within the range of values present , in the selected two’s complement set .
The modulo is calculated with regards to two to the power of bits , used to represent the two’s complement numbers , in binary form , in its two’s complement set .
To detect if the multiplication of two two’s complement number will overflow , it can be done with something like this :
int overflowSignedMultiplication( signed char x , signed char y ){
/*
Check if overflow will occur , when
performing a a two's complement signed
char multiplication .*/if( x == 0 || x == 1 )
return 0 ;// no TC signed multiplication overflowsigned char x_times_y = x * y ;
signed char x_times_y_div_x = x_times_y / x ;if ( x_times_y_div_x == y )
return 0; // no TC signed multiplication overflow
else
return 1 ;/*Two's complement signed multiplication overflow*/}//end overflowSignedMultiplication
Two’s complement division
To perform the division between two , two’s complement numbers , perform a regular division using their integer values . The result is the integer quotient , and any remainder is discarded . Two’s complement division is not defined when dividing by 0 .
Two’s complement division , has only one case for overflow . It happens when dividing the minimum number that can be represented in the two’s complement set , by -1 . In such a case , take the modulo of the result . The modulo is calculated with regards to 2 to the power of the number of bits , used to form the two's complement set .
To detect if the result will overflow , when dividing one two’s complement number by another , it can be done with something like this :
int overflowSignedDivision( signed char x , signed char y ){
/*
Check if dividing y by x , will cause a
two's complement signed char division
overflow .*/signed char is_it_min = y;if( x == -1 && is_it_min < 0 ){
signed char is_it_max = x ^ y;
signed char is_it_max_plus_1 = is_it_max + 1 ;
if ( is_it_max_plus_1 == is_it_min )
return 1; /*TC signed char division overflow */}
return 0;/* No TC signed char division overflow */}
Commutativity , associativity , and distributivity of two’s complement operations
Two's complement addition
commutative : a + b = b + a
associative : a + ( b + c ) = ( a + b ) + cTwo's complement Multiplication
commutative : a * b = b * a
associative : a * ( b * c ) = ( a * b ) * c
distributive over addition and subtraction
a * ( b + c ) = ( a * b ) + ( a * c )
a * ( b - c ) = ( a * b ) - ( a * c )Two's complement Division
not commutative : ( 1 / 2 ) != ( 2 / 1 )
not associative : ( 1 / 2 ) / 3 != 1 / ( 2 / 3 )
because 0 != undefinedTwo's complement Subtraction
not commutative : 1 - 2 != 2 - 1
not associative : -4 - ( -4 - -3 ) != ( -4 - -4 ) - -3
-4 - ( -4 - -3 ) = -4 - -1 = -3
( -4 - -4 ) - -3 = 0 - -3 = 3
One’s complement representation
In the one’s complement algorithm , the number of bits to form the one’s complement set are chosen , the first bit to the left represents , a negative magnitude , while the remaining bits represent, a positive magnitude .
This algorithm is not commonly used nowadays .
Sign and magnitude representation
In the sign and magnitude representation , the number of bits to form the sign and magnitude set are chosen . The first bit to the left , is used for the sign representation , and the rest of the bits are used for the magnitude .
So to represent a number , using the sign and magnitude algorithm , its sign is represented using , the leading left bit , and its magnitude is represented using , the magnitude bits .
This algorithm is not commonly used in computers nowadays .
Signed representations in C
The C standard does not specify , if the signed representation is to be a two's complement one , a one's complement one , or a sign and magnitude one .
Commonly what is used by most of the computers and the compilers , is the two’s complement representation .
By default , the integer data types in C are signed , with the exception of the char type . As such , it is not necessary to precede an integer type , with the signed keyword . Whether the char type is signed , or unsigned , is left for the implementation to decide .
The C , C++ signed integer data types are :
signed char
# typically 8 bits .
# at least 8 bits .signed short
# typically 16 bits .
# at least 16 bits .signed int
# typically 32 bits .
# at least 16 bits .signed long
# typically 64 bits
# at least 32 bits .signed long long
# typically 64 bits
# at least 64 bits .
Originally published at https://twiserandom.com on December 6, 2020.
