CS W3139-02 Data Structures and Algorithms -- Spring 1999

Recitation 3 - Signed Number Binary Represenation Supplement

Signed Number Representation
Signed Magnitude
1's Complement
2's Complement
What you need to know for Hmwk 1

Signed Number Representation

For homework 1, programming problem 1, you are required to output the binary representation of a negative number.
All numbers are represented internally as binary numbers.
This supplement is meant to be bare minimum reference on how to represent binary (particularly negative) numbers.

Signed Magnitude Representation

Signed Magnitude Representation uses the Most Significant Bit (MSB) as the sign bit.
The MSB is the leftmost bit in a binary number, so in the binary number 101101, 1 is the MSB.
In Signed Magnitude Representation, the sign of the number is interpreted as follows:
- 0 means Positive
- 1 means Negative
The magnitude is the size of the number irrespective of sign.
For example, the numbers +13 and -13 both have a magnitude of 13.
In Signed Magnitude Representation, the magnitude of a number is stored in N-1 bits and the sign is represented in the MSB, where N is the number of bits used to represent the entire number.

Here is an example using 32-bit integer representation:

    +13  binary representation: 0000 0000 0000 1101
    -13  binary representation: 1000 0000 0000 1101

The problem with this form of representation is that it has two representations for the number 0:

     +0  binary representation: 0000 0000 0000 0000
     -0  binary representation: 1000 0000 0000 0000

1's Complement

Another form of binary representation is called 1's Complement.
To represent a negative number in 1's Complement you simply take the numbers magnitude and flip all the bits (i.e. 1 becomes 0, and 0 becomes 1).

For example:

    +13  binary representation: 0000 0000 0000 1101
    -13  binary representation: 1111 1111 1111 0010

However, this does not resolve our problem of having two representations of zero:

     +0  binary representation: 0000 0000 0000 0000
     -0  binary representation: 1111 1111 1111 1111

2's Complement

Finally, we have the binary representation form called 2's Complement. This is the form you are required to use for programming problem 1.
In order to represent a negative number in 2's Complement you take the numbers magnitude and (1) take the 1's Complement (flip all the bits), and (2) add 1 to the Least Significant Bit (LSB).
The LSB is the rightmost bit.

For example:

     13  binary representation: 0000 0000 0000 1101

(1) Take the 1's Complement of the magnitude (flip the bits):

    -13  1's Complement:  1111 1111 1111 0010

(2) Add 1 to the Least Significant Bit:

    -13  1's Complement:  1111 1111 1111 0010
                          +                 1
                          -------------------
    -13  2's Complement:  1111 1111 1111 0011

Another example:

     12  binary representation: 0000 0000 0000 1100

(1) Take the 1's Complement of the magnitude (flip the bits):

    -12  1's Complement:  1111 1111 1111 0011

(2) Add 1 to the Least Significant Bit:

    -12  1's Complement:  1111 1111 1111 0011
                          +                 1
                          -------------------
    -12  2's Complement:  1111 1111 1111 0100

You will notice that 2's Complement only has one representation of zero.

What you need to know for Hmwk 1

For programming problem 1 you are required to make you program function for negative numbers as well.
You should represent the negative numbers in 2's Complement form. In addtion to this you should fix the number of bits you output for a negative number to be 32 (in Java, integers are 32-bits).
It is not necessary to pad postive numbers with 0's.
You should revise your test case to include negative numbers.
Read newsgroup for more further specifications for problem 1.

[ CS3139 Home]

CS W3139-02 Data Structures and Algorithms -- Spring 1999

Recitation 3 - Signed Number Binary Represenation Supplement

Contents

Signed Number Representation

Signed Magnitude Representation

1's Complement

2's Complement

What you need to know for Hmwk 1