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 addition

  signed 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 overflow 

  signed 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 ) + c  


Two'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      !=   undefined 


Two'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 .