What is a signed number ?

 

The question, what is a signed number, is actually the question, of how to represent negative, zero, and positive integers, in a computer.

An integer is for example, -1 or 1, or 0, so in other words, it is any numerical value, belonging to the set Z, which is the set containing whole numbers.

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.

For all these algorithm, the computer has a limited memory, so the encoding is performed on a limited number of bits.

Two’s complement representation

What is a Two’s complement number?

A two’s complement number, has an integer value, and an encoding. The integer value, belongs to the set Z , and the encoding is performed on a given number of bits, since a computer memory is limited.

This being said, a two’s complement number encoding, has a format, under which, the most significant bit, has a value of :

And the remaining bits, are taken to be in the binary positional numeral system.

So what this means, is that the first bit of the encoding, can either be a zero, or a negative value, and that the remaining bits, can either be a zero, or a positive value. In other words, the encoding has two parts, a negative, and a positive one, and the integer value which is encoded, is the sum of these two parts.

So to illustrate this, let us say, that encoding is performed using only four bits, then the most significant bit, or the negative part, can have the following values.

The remaining bits, which is the last three bits, can have the following values.

And the possible integer values, that can be represented using four bits encoding are:

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 to ask is, what are the properties of the operations, that can be performed on a two’s complement set, but before discussing this, in later sections, let us first give examples, of how to convert an integer, into its two complement form, so how to encode it, and how to decode an integer, from its two complement form encoding.

Converting an integer, to its two complement form, 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 x, first get p, where p is equal to 1 plus the power of two which is larger or equal to the absolute value of x . Next calculate the value mod , which is equal to 2 to the power of p. Next, add x to the calculated mod value, to obtain the comp value.

Finally, represent this comp value, in the binary positional numeral system. This representation is the two’s complement, binary representation of x. An example to illustrate this:

To convert from two’s complement binary form, to an integer value, it can be done, by multiplying each bit by 2 to the power i, where i is equal to 0,1,2..

Once this is done, subtract the converted value, of the most significant bit , from the sum of the remaining bits.

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 detect, if an overflow will occur, while performing addition in two’s complement, it can be done with something like this:

int overflow_signed_addition( 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*/}

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 detect if a two’s complement subtraction will cause an overflow, it can be done with something like this.

int overflow_signed_subtraction( 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*/;} 

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 overflow_signed_multiplication( 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*/}

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 overflow_signed_division( 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

For one’s complement, the most significant bit, represents a negative magnitude, while the remaining bits, represent a positive magnitude.
The negative magnitude represented in one’s complement, is less by one, than the negative magnitude represented in two’s complement. This is explained in more details, in the following example.

This algorithm is not commonly used nowadays.

Sign and magnitude representation

In the sign and magnitude representation, the most significant bit, is used as a sign bit, when this sign bit is set to 0, this means that the number is positive, and if it is set to 1, this means that the number is negative. The remaining bits, are used for magnitude, so for representing a value.

This algorithm is also 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.