0
\$\begingroup\$

I'm a CS student and I just started my course on basic digital electronics. I'm having some trouble figuring out how binary subtraction works when you have more than one subtrahend, and you need to use more than one "borrow-in". For example, what would be the correct way to solve this:

101011 -001011 001111 --------

Currently, my solution is: sum both substrahends and then I get the most basic case of a minuend and a substrahend. However I was wondering if there was other solutions.

\$\endgroup\$
  • \$\begingroup\$ Usual subtraction takes two operands. So for A-B-C, do (A-B) -> X then, X-C -> Y. Further rules of arithmetic specify it is (A-B)-C, and not (A-(B-C)). This is the normal way of doing arithmetic because it works in more complex situations, by applying commutativity, associative, etc. \$\endgroup\$ – gbulmer Sep 20 '14 at 16:16
  • \$\begingroup\$ In binary arithmetics, subtractions have practically the same complexity as additions, so the order does not matter much : (A-B)-C is equivalent to A-(B+C) \$\endgroup\$ – TEMLIB Sep 20 '14 at 16:19
  • \$\begingroup\$ @TEMLIB - I think that comment is very misleading because a) they do not have the same complexity, and b) the order of operation is crucial. A-B-C must be (A-B)-C, and not (A-(B-C)) for normal arithmetic rules. \$\endgroup\$ – gbulmer Sep 20 '14 at 16:22
  • \$\begingroup\$ @TEMLIB - Okay, you have changed your comment. So, how is A-B-C-D+E-F-G parsed? \$\endgroup\$ – gbulmer Sep 20 '14 at 16:25
  • \$\begingroup\$ The thing is that in the decimal arithmetics you can operate (47-11-15)=17 directly without having to do (47 - (11+15)). I'm asking how would one do the same in binary arithmetics. \$\endgroup\$ – dr_no Sep 20 '14 at 16:48
1
\$\begingroup\$

Binary subtraction is usually implemented using binary addition, and negation.

It is unusual to do three or more operations simultaneously (other than multiply add, aka multiply accumulate, or MAC).

So A-B-C, is usually implemented as A+(-B)+(-C) where the - is unary minus, or negation.

This scales to many operands and many subtrahends.

A-B-C-D+E-F-G becomes A+(-B)+(-C)+(-D)+E+(-F)+(-G). The addition, '+' operation is commutative, so this can be evaluated in any order (ignoring overflow), and with arbitrarily many operands.

How might we operate on \$47-15+23-11+16-22+12\$?
One approach might be \$47+23+16+12-(15+11+22)\$, but how much hardware might be needed to implement that?

Clearly a nifty solution is \$47+(16-15)+(23-22)+(16-15)=50\$, but so what? How much hardware or VHDL and programmable logic would it take to recognise that? When we know in advance the sequence of operations, then optimisations may make sense.

Using 1's complement representation, the rightmost, 'top' bit represents the sign, with '1' indicating a negative number. So to negate a number, 'invert' its top bit to be the other value. A problem with 1's complement representation is their are two zero's a positive (top bit 0) and a negative (top bit 1) representation, which makes some operations more complex.

Most computing uses 2's complement representation of binary numbers. The top bit still indicates the sign ('0' for positive, and '1' for negative) as in 1's complement. However, the values are represented in a slightly different way.

The process is described at Wikipedia Two's complement

To subtract a number, convert to its two's complement form then add. This is a bit weird, but isn't too bad to implement.

This approach has several useful properties:

  • there is only one representation of zero, and hence
  • comparing a number against zero is simpler than 1's complement
  • once the number is converted to its complement, the addition is Commutative, it can be done is either order

Edit:
An efficient way to implement subtraction by calculating the 2's complement adding is:

  1. invert each bit of the subtrahend. Cost one NOT gate per bit. The invert operation has quite a low propagation delay, then
  2. add using N-bit-addder with a '1' carry-in at the bottom bit. The carry-in implements the second 2's complement step of +1.

So the total extra cost of subtraction is N NOT-gates, and the lowest bit of the N-bit-add is a full adder instead of a half adder (which is the classic way to teach this), and hence is an extra three gates.

A useful property of restricting operations to two operands at a time is it works for all cases, and is relatively easy to parse, and apply 'everyday' arithmetic rules of precedence (multiply before add), associativity (left to right) and commutativity (A+B = B+A, but A-B ≠ B-A).

\$\endgroup\$
  • \$\begingroup\$ I'm aware that the two's complement is the recommend approach when implementing substraction in a logical circuit, however what i'm really curious about is the pure arithmetical procedure. \$\endgroup\$ – dr_no Sep 20 '14 at 16:51
  • \$\begingroup\$ What does "pure arithmetical procedure" mean? On the face of it, doing a negation of each individual subtrahend, then adding seems to be the most flexible possible approach. For example it can be scaled to arbitrarily many operands (edited my answer). Am I missing something? \$\endgroup\$ – gbulmer Sep 20 '14 at 16:55
  • \$\begingroup\$ When I say "pure arithmetical procedure" I mean a procedure to make the substraction that doesn't imply using complements or the adition of the substrahends, just like you would do in decimal arithmetics when you solve things like: 47-11-15. Surely, you could use 9's complements or you could choose to do 47-(11+15). However, in most cases we don't, we just use substraction and borrow-ins. I do undestand that such procedure isn't the most effective or the most popular. \$\endgroup\$ – dr_no Sep 20 '14 at 18:04
  • \$\begingroup\$ I would not typically parse X-Y-Z as X-(Y+Z), I'd do (X-Y)-Z, unless I know ahead of time that it's all subtractions. Even then, I might do it one operation at a time, and track my working in case I made a mistake, or there could be doubt about any step. I worked in the retail trade when I was younger, and we didn't use a calculator or a till to do the arithmetic. The information arrived serially, because it was spoken (3 pints of bitter, 2 pints and a 1/2 of lager, … ooops, no make that 1 and a 1/2 of lager, and a bottle of …). IMHO the rationale of sequential operation still applies. \$\endgroup\$ – gbulmer Sep 20 '14 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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