Where did the leading 1 means negative number in signed int arise from?

Question

Even though I read a number of articles that say that mostly 2's complement is used to represent the negative numbers in a signed integer and that that is the best method,

However for some reason I have this (below) stuck in my head and can't get rid of it without knowing the history of it

"Use the leading bit as 1 to denote negative numbers when using signed int."

I have read many posts online & in StakOverflow that 2's complement is the best way to represent negative numbers. But my question is not about the best way, it is about the history or from where did the "leading bit" concept arise and then disappear?

P.S: Also it is just not me, a bunch of other folks were also getting confused with this.

Edit - 1 The so called leading 1 method I mentioned is described with an example in this post: Why is two's complement used to represent negative numbers?

Now I understand, the MSB of 1 signifies negative numbers. This is by nature of 2's complement and not any special scheme.

Eg. If not for the 1st bit, we can't say if 1011 represents -5 or +11.

Thanks to: jamesdlin, Oli Charlesworth, Mr Lister for asking imploring questions to make me realize the correct answer.

Rant: I think there are a bunch of groups/folks who have been taught or been made to think (incorrectly) that 1011 evaluates to -3. 1 denoting - and 011 denoting 3.

The folks who ask "what my question was.. " were probably taught the correct 2's complement way from the first instance they learnt it and weren't exposed to these wrong answers.

Answer 1

There are several advantages to the two's-complement representation for signed integers.

Let's assume 16 bits for now.

Non-negative numbers in the range 0 to 32,767 have the same representation in both signed and unsigned types. (Two's-complement shares this feature with ones'-complement and sign-and-magnitude.)

Two's-complement is easy to implement in hardware. For many operations, you can use the same instructions for signed and unsigned arithmetic (if you don't mind ignoring overflow). For example, -1 is represented as 1111 1111 1111 1111, and +1 as 0000 0000 0000 0001. If you add them, ignoring the fact that the high-order bit is a sign bit, the mathematical result is 1 0000 0000 0000 0000; dropping all but the low-order 16 bits, gives you 0000 0000 0000 0000, which is the correct signed result. Interpreting the same operation as unsigned, you're adding 65535 + 1, and getting 0, which is the correct unsigned result (with wraparound modulo 65536).

You can think of the leading bit, not as a "sign bit", but as just another value bit. In an unsigned binary representation, each bit represents 0 or 1 multiplied by the place value, and the total value is the sum of those products. The lowest bit's place value is 1, the next lower bit is 2, then 4, etc. In a 16-bit unsigned representation, the high-order bit's place value is 32768. In a 16-bit signed two's-complement representation, the high-order bit's place value is -32768. Try a few examples, and you'll see that everything adds up nicely.

See Wikipedia for more information.

Answer 2

It's not just about the leading bit. It's about all the bits.

Starting with addition

First let's look at how addition is done in 4-bit binary for 2 + 7:

  10 + 
 111
____
1001

It's the same as long addition in decimal: bit by bit, right to left.

• In the rightmost place we add 0 and 1, it makes 1, no carry.
• In the second place from the right, we add 1 and 1, that makes 2 in decimal or 10 in binary - we write the 0, carry the 1.
• In the third place from the right, we add the 1 we carried to the 1 already there, it makes binary 10. We write the 0, carry the 1.
• The 1 that just got carried gets written in the fourth place from the right.

Long subtraction

Now we know that binary 10 + 111 = 1001, we should be able to work backwards and prove that 1001 - 10 = 111. Again, this is exactly the same as in decimal long subtraction.

1001 -
  10
____
 111

Here's what we did, working right to left again:

• In the rightmost place, 1 - 0 = 1, we write that down.
• In the second place, we have 0 - 1, so we need to borrow an extra bit. We now do binary 10 - 1, which leaves 1. We write this down.
• In the third place, remember we borrowed an extra bit - so again we have 0 - 1. We use the same trick to borrow an extra bit, giving us 10 - 1 = 1, which we put in the third place of the result.
• In the fourth place, we again have a borrowed bit to deal with. Subtract the borrowed bit from the 1 already there: 1 - 1 = 0. We could write this down in front of the result, but since it's the end of the subtraction there's no need.

There's a number less than zero?!

Do you remember how you learnt about negative numbers? Part of the idea is that you can subtract any number from any other number and still get a number. So 7 - 5 is 2; 6 - 5 is 1; 5 - 5 is 0; What is 4 - 5? Well, one way to reason about such numbers is simply to apply the same method as above to do the subtraction.

As an example, let's try 2 - 7 in binary:

     10 -
    111
_______
...1011

I started in the same way as before:

• In the rightmost place, subtract 1 from 0, which requires a borrowed bit. 10 - 1 = 1, so the last bit of the result is 1.
• In the second-rightmost place, we have 1 - 1 with an extra borrow bit, so we have to subtract another 1. This means we need to borrow our own bit, giving 11 - 1 - 1 = 1. We write 1 in the second-rightmost spot.
• In the third place, there are no more bits in the top number! But we know we can pretend there's a 0 in front, just like we would do if the bottom number ran out of bits. So we have 0 - 1 - 1 because of the borrow bit from second place. We have to borrow a bit again! Anyway we have 10 - 1 - 1 = 0, which we write down in the third place from the right.

• Now something very interesting has happened - both the operands of the subtraction have no more digits, but we still have a borrow bit to take care of! Oh well, let's just carry on as we have been doing. We have 0 - 0, since neither the top or bottom operand have any bits here, but because of the borrow bit it's actually 0 - 1.

  (We have to borrow again! If we keep borrowing like this we'll have to declare bankruptcy soon.)

  Anyway, we borrow the bit, and we get 10 - 1 = 1, which we write in the fourth place from the right.

Now anyone with half a mind is about to see that we are going to keep borrowing bits until the cows come home, because there ain't no more bits to go around! We ran out of them two places ago if you forgot. But if you tried to keep going it'd look like this:

...00000010
...00000111
___________
...11111011

• In the fifth place we get 0 - 0 - 1, and we borrow a bit to get 10 - 0 - 1 = 1.
• In the sixth place we get 0 - 0 - 1, and we borrow a bit to get 10 - 0 - 1 = 1.
• In the seventh place we get 0 - 0 - 1, and we borrow a bit to get 10 - 0 - 1 = 1.

...And so it goes on for as many places as you like. By the way, we just derived the two's complement binary form of -5.

You could try this for any pair of numbers you like, and generate the two's complement form of any negative number. If you try to do 0 - 1, you'll see why -1 is represented as ...11111111. You'll also realise why all two's complement negative numbers have a 1 as their most significant bit (the "leading bit" in the original question).

In practice, your computer doesn't have infinitely many bits to store negative numbers in, so it usually stops after some more reasonable number, like 32. What do we do with the extra borrow bit in position 33? Eh, we just quietly ignore it and hope no one notices. When some does notice that our new number system doesn't work, we call it integer overflow.

Final notes

This isn't the only way to make our number system work, of course. After all, if I owe you $5, I wouldn't say that your current balance with me was $...999999995.

But there are some cool things about the system we just derived, like the fact that subtraction gives you the right result in this system, even if you ignore the fact that one of the numbers is negative. Normally, we have to think about subtractions with conditional steps: to calculate 2 - 7, we first have to figure out that 2 is less than 7, so instead we calculate 7 - 2 = 5, and then stick a minus sign in front to get 2 - 7 = -5. But with two's complement we just go ahead do the subtraction and don't care about which number is bigger, and the right result comes out by itself. And others have mentioned that addition works nicely, and so does multiplication.

Answer 3

You don't use the leading bit, per say. For instance, in an 8-bit signed char,

11111111

represents -1. You can test the leading bit to determine if it is a negative number.

There are a number of reasons to use 2's complement, but the first and greatest is convenience. Take the above number and add 2. What do we end up with?

00000001

You can add and subtract 2's complement numbers basically for free. This was a big deal historically, because the logic is very simple; you don't need dedicated hardware to handle signed numbers. You use less transistors, you need less complicated design, etc. It goes back to before 8-bit microprocessors, which didn't even have multiply instructions built-in (even many 16-bit ones didn't have them, such as the 65c816 used in apple IIe and Super NES).

With that said, multiplication is relatively trivial with 2's complement also, so that's no big deal.

Answer 4

Complements (including things like 9s complement in decimal, mechanical calculators / adding-machines / cash registers) have been around forever. In nines' complement with four decimal digits, for instance, values in the range 0000..4999 are positive while values in 5000..9999 are negative. See http://en.wikipedia.org/wiki/Method_of_complements for details.

This directly gives rise to 1s complement in binary, and in both 1s and 2s complement, the topmost bit acts as a "sign bit". This does not explain exactly how computers moved from ones' complement to two's complement (I use Knuth's apostrophe convention when spelling these out as words with apostrophes, by the way). I think it was a combination of luck, irritation at "negative zero", and the way ones' complement requires end-around carry (vs two's complement, not requiring it).

In a logical sense, it does not matter which bit you use to represent signs, but for practical purposes, using the top bit, and two's complement, simplifies the hardware. Back when transistors were expensive, this was pretty important. (Or even tubes, although I think most if not all vacuum-tube computers used ones' complement. In any case they predated the C language by rather a lot.)

In summary, the history goes back way before electronic computers and the C language, and there was no reason to change from a good way of implementing this mechanically, when converting from mechanical calculators to vacuum-tube ENIACs to transistorized computers and then on to "chips", MSI, LSI, VLSI, and onward.

Answer 5

Well, it had to work such that 2 plus -2 gives zero. Early CPUs had hardware addition and subtraction and someone noticed that by complementing all the bits (one's complement, the original system), to change the "sign" of the value, it allowed the existing addition hardware to work properly—except that sometimes the result was negative zero. (What is the difference between -0 and 0? On such machines, it was indeterminate.)

Someone soon realized that by using twos-complement (convert a number between negative and positive by inverting the bits and adding one), the negative zero problem was avoided.

So really, it is not just the sign bit which is affected by negatives, but all of the bits except the LSB. However, by examining the MSB, one can immediately determine whether the signed value there is negative.