Dealing with Binary

Thread Starter

amishjeb

Joined Sep 9, 2012
14
I'm having some issues getting the one's complement of some numbers. Well... I'm having some trouble believing I'm right and the answer key to the book is wrong.

Here is the question: Convert the decimal number 73 into signed 12-bit numbers in the following representations:
(a) Sign and magnitude
(b) 1's complement
(c) 2's complement

(a) For the binary representation of 73 (and changing it to 12-bit) I got 000001001001.

(b) Getting the 1's complement, I'm complementing each bit so I'd get 111110110110.

(c) Getting the 2's complement, I'm taking the 1's complement and then adding one to the LSB and getting 111110110111.

The answer key confirms part (a) but shows the same binary number for the remaining three parts. So am I wrong and missing something obvious here or is the key wrong?
 

Thread Starter

amishjeb

Joined Sep 9, 2012
14
for positive numbers, 1s complement and 2s complement are identical.

check this link
I've come to realize that now after looking at a ton of examples, but I don't understand why.

PS. Hope that didn't come across as short, just frustrated that I can't figure out why.
 
Last edited:

WBahn

Joined Mar 31, 2012
29,979
All three have identical representations for positive numbers - that's one of the major goals of crafting a useful signed representation.

The algorithm you are using for 1's and 2's complement is specificly intended for determining the representation for a NEGATIVE integer in those representations.

There are lot's of ways to look at it, but perhaps this will help.

Let's take a 3-bit representation for unsigned binary:

Pattern|straight
000|0
001|1
010|2
011|3
100|4
101|5
110|6
111|7

All this really is a mapping between a bit pattern and the value we choose to associate with that pattern. This particular mapping only has non-negative integers in it. But what if we want to have a mapping that is split with about half positive and half negative numbers and what if we want to keep the same patterns for any non-negative integers? We have a number of options.

Signed binary: To get the representation for a negative value, just take the representation for the absolute value and flip the most significant bit.

Pattern|signed
000|0
001|1
010|2
011|3
100|-0
101|-1
110|-2
111|-3

1's Complement: To get the representation for a negative value, just take the representation for the absolute value and flip all the bits:

Pattern|1's
000|0
001|1
010|2
011|3
100|-3
101|-2
110|-1
111|-0

But these both have problems, not the least of which is that circuits to perform arithmetic on the unsigned binary representation is simple, fast, and cheap. But the circuits to perform arithmetic on the above signed representations would be complex, slow, and expensive (relatively speaking).

But what if we chose a cyclic representation?

When we take an integer and reduce it mod 8, we get a number between 0 and 7 (inclusive). Thus, if we add 7 and 6 we get 5 since (7+6)%8 is 5. The same is true for negative numbers. If our computation results in -3 and we reduce that modulo 8, we get 5 again. In general, any value that can be written as 8k+5, where k is an integer (positive or negative) is "congruent" to 5 in a modulo 8 (i.e., 3-bit) world.

This is the arithmetic that our normal simple, fast, cheap circuits are carrying out. They are working in a mod-8 world and, in that world, -3 and 5 are indistinguishable (and they are equivalent to -11 and 13 and 21 and an infinite number of other integer values). We simply CHOOSE to interpret each pattern with the smallest non-negative value in the set.

What if, instead, we choose to interpret each pattern with the smallest non-negative value in the set if the leading bit is zero and the largest negative value in the set if the leading bit is a one? (here, 'smallest' and 'largest' refer to the number line in which larger values are to the right of smaller values). That results in the following mapping:

Pattern|2's
000|0
001|1
010|2
011|3
100|-4
101|-3
110|-2
111|-1

To get this table, we simply subtracted 8 from each pattern that had the leading bit set.

So what an algorithm for doing this?

IF the value, V, to be represented is negative, we want to use the bit pattern that we associated with the unsigned value V+8 (or, in general, V+2^N where N is the number of bits in the representation).

Since we know that V<0, we can write this as:

V+2^N = 2^N - |V|

We can write this as:

[(2^N - 1) - |V|] + 1

2^N - 1 is simply a pattern of N 1's. If we subtract any value from this pattern, the effect is simply to invert the pattern of the value (since 1-0=1 and 1-1=0). Thus we end up with:

~|V| + 1

where '~' is the bitwise inverse operator.
 
Top