Computer binary bit subtraction

[DylsexicChciken]

My books says that when a computer tries to subtract a large binary number form a small binary number, the computer attempts to borrow from leading 0s, and the result is a string of leading 1s. Why is this the case, especially when the smaller number don't have leading 1s to accommodate the subtraction? So how can the result be leading 1s as if the smaller number was bigger? What is happening in the hardware that forces the computer to create a string of leading 1s?

Edited February 13, 2015 by DylsexicChciken

[Strange]

In hardware, subtraction is normally done in the ALU by using an adder and negating the input to be subtracted.

 

As most computers use 2s-complement to represent negative numbers, negating a number means inverting all the bits (easy) and then adding 1. To avoid a separate addition step, the ALU inverts the input to the adder and feeds in an extra 1 to the low order bit. This allows the negation and addition to be done at the same time. (Having the ability to feed in a 1 also makes it easy to use the adder iteratively to work on longer numbers - the carry out of one iteration is fed in to the next.)

[Enthalpy]

Computers represent numbers on a finite number of bits, for instance 32. When an integer result is outside the range of possible values, it gets truncated to the lower bits. In other words, the result is represented modulo 2^32.

 

When subtracting a big number from a small one, the result modulo 2^32 is almost the "normal" result - it is just 2^32 bigger, hence the leading ones. This is the proper result to be expected, and most standards define it that way. The computer couldn't give a "better" result anyway.

 

Interesting: the same range defined by 32 bits can represent a signed integer just as well. The most usual convention (called complement to 2... not used with float numbers!) is that a signed integer goes from -2^31 to +(2^31)-1 inclusive. Then, the same hardware does the +-*/ operations properly, without any modification, on unsigned and on signed integers. From your example, the leading ones tell that the difference is negative, just fine.

 

The only difference is how the computer tells if the operation has gone past the range. Usually, it sets an "overflow" bit if the unsigned range is exceeded and a "carry" if the signed range is exceeded.

 

A few compilers propose to check at every operation if the range was exceeded; some do it as a default, most don't. The C standard is to avoid checking, since this is faster on most machines, and aware programmers make use of this as a feature.

[Enthalpy]

Maybe a parallel would make modulo and signed arithmetic clearer.

 

Imagine that we count hours from 0 to 23 beginning at midnight - and forget the minutes altogether. This is cyclic arithmetic, that is, 23+2=1 instead of 25. We compute modulo 24 just like a 16-bit machine computes modulo 65536.

 

Now, we could prefer to count the afternoon hours as the remaining time until midnight. 1PM would be -11, 6PM is -6, 11PM is -1. This is just the conventional value we attribute to the numbers, which are still represented by the same positions of pebbles on the ground, hand angles on the watch, bits combinations in the machine. We have just invented signed numbers. Signed hours run now, just by convention, from -12 to +11, while unsigned hours ran between 0 and 23.

 

The original question subtracted one from zero. When time is unsigned, one hour before midnight is 23. When time is signed, it is -1 hour.

 

Whether we consider it 23 or -1 depends on how we interpret the same hand angles on the watch. In a computer too, it's the same combination of bits that is interpreted as unsigned or signed integer.

 

And on a 16 bit machine, "one less than zero" means "one less than 65536" or 65535, which is the biggest number that can be represented as unsigned integer, with all bits at 1. If interpreted as a signed integer, this combination of bits means -1.