10

I know it has something to do with 2's complement and adding 1, but I don't really get how you can encode one more number with the same amount of bits when it comes to negative numbers.

2
  • 3
    The really nasty part of this is that Abs(MinValue) is negative.
    – OldFart
    Jan 9, 2013 at 22:47
  • 1
    in java Double.MIN_VALUE is the smallest positive value, and the (real) numbers furthest away from zero have equal magnitude (as it has a proper sign bit) Jan 10, 2013 at 1:11

3 Answers 3

16

Think about it in these terms. Take a 2-bit number with a preceding sign:

000 = 0
001 = 1
010 = 2
011 = 3

Now let's have some negatives:

111 = -1
110 = -2
101 = -3

Wait, we also have

100 ... 

It has to be negative, because the sign-bit is 1. So, logically, it must be -4.

(Edit: As WorldEngineer rightly points out, not all numbering systems work this way -- but the ones you're asking about do.)

10

Because there are not two classes of numbers in the integer range, but three: negative numbers, zero, and positive numbers. Zero has to take up a slot (would be rather impractical not to be able to represent zero...), so either the positive or the negative class has to give up a slot. The fact that it's usually the positive range that has to make that sacrifice is to a certain extent arbitrary, but on the level of bit manipulations there are some things that this decision makes more convenient.

1
  • It's not just bit manipulations. The set of 32-bit signed numbers is the set of numbers whose binary representation has the same value in all bits after the 31st, and one such number has an infinite set of ones followed by 31 zeroes. The additive inverse of that number, an infinite string of zeroes followed by a single 1 and 31 zeroes, does not fit the pattern required of signed values.
    – supercat
    May 27, 2014 at 23:11
4

There are BASICALLY three ways to represent signed integers in binary: 2's complement, 1's complement, and sign-magnitude. (Biquinary went the way of the Dodo Bird a long time ago.)

1's complement and sign-magnitude have two zero values, +0 and -0, each with a unique representation. 2's complement only has one zero value, and one representation.

Now, a field of N bits can encode 2^N values. Subtract one in 2's complement, and you have 2^N-1 = 2^(N-1) + 2^(N-1) + 1. Since the representation for zero is all zero bits, and a + sign is zero, there will be one more possible nonzero representation with the sign bit set to 1.

This is a very long-winded way of saying 2's complement represents values in the range -(2^(N-1)) .. +(2^(N-1) - 1).

1's complement actually has an advantage over 2's complement if you are doing integer digital signal processing computations. 1's complement operations inherently truncate toward zero. 2's complement truncates toward -infinity. I learned this one the HARD way...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.