8/13/24, 8:43 AM CS W3139-02 Recitation 3 Supplement
CS W3139-02 Data Structures and Algorithms --
Spring 1999
Recitation 3 - Signed Number Binary
Represenation Supplement
Contents
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:
https://www.cs.columbia.edu/~nieh/teaching/w3139_s99/recitation/recitation3-supp.html#:~:text=The magnitude is the size,to represent the entire … 1/3
8/13/24, 8:43 AM CS W3139-02 Recitation 3 Supplement
+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
https://www.cs.columbia.edu/~nieh/teaching/w3139_s99/recitation/recitation3-supp.html#:~:text=The magnitude is the size,to represent the entire … 2/3
8/13/24, 8:43 AM CS W3139-02 Recitation 3 Supplement
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]
https://www.cs.columbia.edu/~nieh/teaching/w3139_s99/recitation/recitation3-supp.html#:~:text=The magnitude is the size,to represent the entire … 3/3
