Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
How to do +, -, *, / with number in a base b?
Subtraction of numbers with arbitrary bases

This is a very basic question. But I come from non computer science background and is having trouble understanding this . Lets say I want to subtract two binary numbers (say 100 - 001 = 011). How do I go about doing this subtraction ? Please provide an analogy for a decimal subtraction

P.S: Actually I found out that the HashMap in Java requires its bucket size to be a power of 2 and finds the bucketIndex by the following code and this works well if n is a power of 2 . h is the value of the key to be hashed and length is number of buckets in the HashMap

static int indexFor(int h, int length) {
    return h & (length-1);
}

So I am assuming that that n here is 4 . So lets say we do 4-1 =3 which is 011 in binary .I am getting confused with borrowing operation here for the 2's place and 4's place during the subtraction process.

share|improve this question

marked as duplicate by MJD, sdcvvc, William, tomasz, t.b. Sep 10 '12 at 21:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

1 Answer 1

up vote 4 down vote accepted

You go for that subtraction exactly as you would do for decimal, except that you need to borrow already for $2=$10. So for your example, you have

  100
- 001
      <- place for borrows
  ___

So you start in the rightmost column, where you have $0-1$. Since $0<1$, you have to borrow from the left, so you have 10-1 that is $2-1$ which is $1$. So after this step, you end up with

  100
- 001
   1
  ___
    1

Now to the second solumn. Again, including the borrow, you have to subtract $1$ from $0$, so you need to borrow again. Again, you'll get 10-1$=2-1=1$:

  100
- 001
  11
  ___
   11

Finally, with the left column, you have $1-1$, which doesn't need a borrow and gives $0$. So you end up with

  100
- 001
  11
  ___
  011

Which evidently is the correct result.

However it may be easier to first only collect the borrows and then subtract them in a separate step (continuing until no borrows are left). Note that this could be done in decimal subtraction as well. With that algorithm you collect the borrows below the preliminary result, and then restart the subtraction algorithm. This is especially useful for problems like 100-011 where the borrow gets larger than $1$. Here's how that method works:

  100
- 011
  ___
       <- Preliminaty result
    0  <- Borrows (initialized with a rightmost 0)

First, subtract the right-most column. This needs a borrow, which this time is noted below.

  100
- 011
  ___
    1
   10

Now we get to the second column. With the previous algorithm, you'd have to subtract $10$=2$, which is of course possibile with borrow, but you need to think a little bit more (which is especially bad if you are a computer and thus quite stupid). With this second algorithm, you just ignre the borrow for the moment, and subtract the second column normally (which again gives a borrow).

  100
- 011
  ___
   11
  110

Finally you subtract the leftmost column, which works without a borrow:

  100
- 011
  ___
  111
  110

Now the borrows are not empty, therefore you have to subtract them. Fortunately you know how to do that:

  100
- 011
  ___
  111
- 110
  ___
  001

Voila, the correct result!

OK, so why is this algorithm better? Well, because you never get a borrow larger than $1$, and since computers are especially good with $0$ and $1$, this is better suited for them. Moreover, if you look at the preliminary results, you'll find that each bit is 1 exactly if the original bits are different; that operation is known as XOR and is a basic logic operation which can be easily implemented on computers. Also, it is easy to see that the borrow now occurs exactly when the bit of the first number is 0 and the bit of the second number is 1. Which is also a combination of two basic logical operations, NOT and AND.

Also note that the XOR is also valid for addition, only the borrow has to be changed to a carry. A carry happens exactly if both bits are 1. So basically the only difference between binary addition and binary subtraction is a NOT on the first number when calculating the borrow instead of the carry.

share|improve this answer
    
so in step 1 I am borrowing a 2 from the 2'splace of the upper number right ? Also "except that you need to borrow already for 2=10" . What does this mean ? –  Geek Aug 22 '12 at 13:22
    
Yes, that's right. And if you look closely, I've written $2$ in math mode, and 10 in code mode. What I mean is the number $2$, written in binary as 10. –  celtschk Aug 22 '12 at 13:42
add comment

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