Where does the beginning 1 come from means a negative number in a signed int?

Question

Despite the fact that I read a number of articles that say that basically 2 additions are used to represent negative numbers in the value of an integer and that this is the best method,

However, for some reason, I have it (below) stuck in my head and cannot get rid of it without knowing its history

"Use high bit as 1 to indicate negative numbers when using a signed int."

I read a lot of posts on the Internet and on StakOverflow that 2 add-ons are the best way to represent negative numbers. But my question is not in the best way, but in history, or where did the "lead bit" concept come from, and then disappear?

PS: And it's just not me, a bunch of other people are also confused with this.

Edit - 1 The so-called lead 1 method that I mentioned is described as an example in this post: Why are two additions used to represent negative numbers?

Now I understand that MSB 1 stands for negative numbers. This is inherently 2 additions, and not any special scheme.

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

Thanks: jamesdlin, Oli Charlesworth, Mr. Lister for asking me to persuade me to understand the correct answer.

Rant: I think there is a group of groups / people who have been taught or made to think (wrong) that 1011 rates -3. 1 is - and 011 is 3.

People who ask the question “what was my question ...” probably taught the correct option 2 of the supplement from the first copy that they studied, and did not undergo these incorrect answers.

Answer 1

There are several advantages of representing two additions for signed integers.

Assume 16 bits now.

Negative numbers in the range from 0 to 32,767 have the same representation in both signed and unsigned types. (Two's-complement shares this feature with one-complement and signs and values.)

The "two" add-ons are easy to implement on hardware. For many operations, you can use the same instructions for signed and unsigned arithmetic (unless you 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 a high order bit is a signed bit, the mathematical result is 1 0000 0000 0000 0000 ; discarding everything except the lower 16 bits gives you 0000 0000 0000 0000 , which is the correct result. Interpreting the same operation as unsigned, you add 65535 + 1 and get 0 , which is the correct unsigned result (with wraparound modulo 65536).

You can think of a leading bit, not as a “sign bit,” but as a different bit value. In an unsigned binary representation, each bit represents 0 or 1 times the location value, and the total value is the sum of these products. The smallest bit space is 1, the next least significant bit is 2, then 4, etc. In a 16-bit unsigned representation, the placement value in high 32768 . In a 16-bit signed representation with two additions, the high-order bit space value is -32768 . Try a few examples and you will see that everything is beautiful.

See Wikipedia for more details.

Answer 2

It is not only a leading bit. This is about all the bits.

Starting from add

First, let's see how the addition is done in a 4-bit binary for 2 + 7:

  10 + 111 ____ 1001 

This is the same as the long addition in decimal format: bitwise, from right to left.

• In the far right place we add 0 and 1, it does 1, does not transfer.
• In the second place on the right, add 1 and 1, which makes 2 in decimal or 10 in binary format - we write 0, carry 1.
• In the third place on the right, add 1, which we moved to 1 already there, it makes binary code 10. Write 0, carry 1.
• The 1 that you just received is written in fourth place on the right.

Long subtraction

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

 1001 - 10 ____ 111 

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

• In the rightmost place, 1 - 0 = 1, write down.
• Secondly, we have 0 - 1, so we need to take an extra bit. Now we make a binary 10 - 1 that leaves 1. We write this.
• Third, remember that we borrowed an extra bit - so we have 0 - 1 left. We use the same trick to borrow an extra bit, giving us 10 - 1 = 1, which we put in third place.
• Fourth, we again have a leverage for the solution. Subtract the borrowed bit from the existing one: 1 - 1 = 0. We could write this before the result, but since this is the end of the subtraction, there is no need.

Is there a number less than zero ?!

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

As an example, try 2 - 7 in binary format:

  10 - 111 _______ ...1011 

I started the same way as before:

• In the far right 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 bit of borrowing, so we need to subtract another one. This means that we need to borrow our own bit, giving 11 - 1 - 1 = 1. We write 1 in the second rightmost place.
• Thirdly, there are no more bits in the top number! But we know that we can make the view 0 in front, as we would if the lower number ended a bit. So we have 0 - 1 - 1 due to the battle of borrowing from second place. We need to lend again! In any case, we have 10 - 1 - 1 = 0, which we write in third place on the right.

• Now something very interesting has happened - both subtraction operands have no more digits, but we still have a borrowing bit to take care! Well, let me just continue on as we did. We have 0 - 0, since neither the upper nor the lower operand has any bits here, but because of the borrow bit it is actually 0 - 1 ..

  (We must borrow again! If we continue to borrow, we will have to declare bankruptcy soon.)

  In any case, we take a bit and get 10 - 1 = 1, which we write in fourth place on the right.

Now everyone who has half the mind will see that we will continue to borrow bits until the cow returns home, because there are no more pieces! We ran out of them two places back if you forgot. But if you try to continue, it will look like this:

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

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

... And so it goes on for many places as you like. By the way, we just output the binary binary form -5.

You can try this for any pair of numbers that you like, and create two forms of complement to any negative number. If you try to make 0 - 1, you will see why -1 is represented as ...11111111 . You will also understand why all two negative complement numbers have 1 as the most significant bit (the “leading bit” in the original question).

In practice, your computer does not have infinitely many bits to store negative numbers, so it usually stops after some more reasonable number, for example 32. What do we do with the extra bit at position 33? Eh, we just quietly ignore him and hope that no one will notice. When some people notice that our new number system is not working, we call it an integer number of overflows .

Final notes

This is not the only way to make our number system, of course. In the end, if I owe you $ 5, I would not say that your current balance with me was $ 999999995.

But there are some interesting things about the system that we just deduced, for example, the fact that subtraction gives you the correct result in this system, even if you ignore the fact that one of the numbers is negative. Usually we should think about subtractions with conditional steps: to calculate 2 - 7, we first need to find out that 2 is less than 7, so instead we calculate 7 - 2 = 5, and then insert the minus sign in front to get 2 - 7 = -5. But with two additions, we simply continue to do the subtraction and do not care about which number is greater, and the correct result is obtained by itself. And others mentioned that adding works beautifully as well as multiplying.

Answer 3

You do not use the leading bit, for example. For example, in an 8-bit char subscription,

11111111

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

There are several reasons to use 2 add-ons, but the first and most convenient. Take the above number and add 2. What will we get?

00000001

You can add and subtract 2 add-on numbers mostly for free. This was historically historically because the logic is very simple; You do not need dedicated equipment to process signed numbers. You use less transistors, you need a less complex design, etc. He goes back to 8-bit microprocessors that didn't even have many built-in instructions (even many 16-bit ones didn't have the 65c816 used in apples IIe and Super NES).

With that said, multiplication is relatively trivial and with 2 additions, so it doesn't matter.

Answer 4

Add-ons (including things like 9s decimal, mechanical calculators / add-ons / cash registers) were forever. For example, in the amount of nine additions with four decimal places, the values ​​in the range 0000..4999 are positive, and the values ​​in 5000..9999 are negative. See http://en.wikipedia.org/wiki/Method_of_complements for more details.

This directly leads to a 1s complement in binary, and in both 1s and 2s, the topmost bit acts as a “sign bit”. This does not explain exactly how computers moved from one supplement to two additions (I use the Quit convention of the apostrophe when writing these words as words with apostrophes). I think it was a combination of good luck, annoyance at a "negative zero", and the way that the "addition" requires a transfer of the end (compared to two additions, without requiring this).

In a logical sense, it does not matter which bit you use to represent characters, but for practical purposes, using the top bit and two additions, simplifies the hardware. Back when transistors were expensive, it was very important. (Or even tubes, although I think that most, if not all vacuum tube computers used them. In any case, they preceded C quite a lot.)

Thus, the story goes back to electronic computers and the C language, and there is no reason to switch from a good way to implement this mechanically when switching from mechanical calculators to ENIAC to vacuum tubes to transistorized computers, and then to “chips”, MSI, LSI, VLSI and further.

Answer 5

Well, it had to work so that 2 plus -2 gives zero. Early processors had hardware addition and subtraction, and someone noticed that, supplementing all the bits (one addition, the original system) to change the "sign" of the value, this allowed the correct functioning of the existing additional equipment, except that sometimes the result is negative zero. (What is the difference between -0 and 0? On such machines, it was uncertain.)

Someone soon realized that using the twos complement (converting a number between negative and positive, inverting bits and adding one), the problem of negative zero was fixed.

So really, this is not only a bit of a sign that is negatively affected, but also all bits except LSB. However, by examining the MSB, you can immediately determine if the sign value has a negative value.