Subtracting signed binary numbers without two's complement

user_3846286 0
Viewed 889

So I'm trying to write code to subtract two binary numbers but I'm not sure how to tackle this problem elegantly. The structures that hold the binary numbers are as follows.

typedef struct _bitb {
    short bit;
    struct _bitb *nbit;
} BitB;
typedef struct _bignum {
    short sign;
    BitB *bits;
} BigNum;

Thus a binary number is represented by a list of bits containing its absolute value, from the LSB to the MSB, and then a short that says whether the number is positive or negative (it's an implementation of arbitrary precision arithmetic). How can I subtract one number from the other without two's complement?

And before someone asks, this is for school, but I don't want a solution in code, just a general algorithm that I can implement. I've been searching around and it seems like there isn't a good algorithm that can solve the general case. Do I need to check the signs of the numbers and then implement code for all the possible cases (negative minus positive, positive minus negative, positive minus positive, negative minus positive)? Or should I just convert to 2's complement?

arbitrary-precision binary c
3 Answers

this is for school, but I don't want a solution in code, just a general algorithm that I can implement

BigNum is a sign-magnitude linked list encoding of an integer.

To add/subtract BigNum, code needs to be made to add/subtract the magnitude of each BitB operand.

To add magnitude, it is simple enough to walk the BitB linked lists and form the sum as you go.

// pseudo-code
BitB *BitBAdd(const BitB *a, const BitB *b) {
  BitB temp_head = set next member to NULL
  BitB *bit_walker = pointer to the head
  bool carry = false;
  while (a is not end of list, b not end of list, or carry) {
    bool abit = get bit from a if not NULL and advance a, else 0
    bool bbit = get bit from b if not NULL and advance b, else 0
    bit_walker->nbit =  malloc(sizeof *(bit_walker->nbit));
    check allocation success
    advance bit_walker
    set bit_walker->nbit members to NULL, abit ^ bbit ^ carry
    carry = majority(abit, bbit, carry);
  }
  return temp_head.nbit;
}

The subtraction of magnitude entails finding the larger one first: int BitBCmp(const BitB *a, const BitB *b). Code not shown. The subtraction function BitB *BitBCmp(const BitB *larger, const BitB *smaller) is then similar to BitBAdd(). Not shown.

Once BitBAdd(), BitBCmp() and BitBSub() are made, then BigNum_Add() and BigNum_Sub() can be made by examining the signs and calling various BitB...() as suggested by @user3386109.

Side issues

BitBAdd() represents about 20-25% of the code needed to fulfill OP's task.

Lopping off of most-significant zero digits may be desired. Also consider sign-magnitude encodings could generate +0 and -0.

user_24103590

You can reduce the problem to two cases: opposite signs and same signs.

Subtracting numbers that have opposite signs requires adding the two absolute values. Examples:

(-7) - (+5) = -(7+5)
(+7) - (-5) = +(7+5)

To subtract numbers that have the same sign, you need to subtract the smaller absolute value from the larger absolute value. Examples:

(+7) - (+5) = +(7-5)
(+7) - (+9) = -(9-7)
(-7) - (-5) = -(7-5)
(-7) - (-9) = +(9-7)

And as you can see there are actually six cases for the sign of the result, as shown below (where X, Y and Z are the magnitude of the number).

(-X) - (+Y) ==> -(Z)
(+X) - (-Y) ==> +(Z)
(+X) - (+Y) and (X >= Y) ==> +(Z)
(+X) - (+Y) and (X <  Y) ==> -(Z)
(-X) - (-Y) and (X >  Y) ==> -(Z)
(-X) - (-Y) and (X <= Y) ==> +(Z)

In summary:

If the two numbers have opposite signs, then add the magnitudes.
If the two numbers have the same sign, then subtract the smaller magnitude from the larger magnitude.
Then determine the sign of the result.

user_33861090

You will need 2's complemement in the case of A-B where |A| < |B|. e.g. if A = 2and B = 5, A-B will be -3 You will have to take the 2's complement of the result. -(5-3). You have to use 2's complement in any case.

I would suggest that you use 2's complement to convert your subtraction into an addition.

i.e. if you have ans = A-B take the 2's complement of B and then add.

You will then get ans = A + (-B).

Step 1. Take 2's complement of B

Step 2. Add A with the 2's complement.

This will simplify the code to a great extent.

Also, this is how subtraction of numbers is handled inside the CPU.

user_35555250
Related